GAP 4.8.9 installation with standard packages -- copy to your CoCalc project to get it
#############################################################################
##
#W sigs.gi RDS Package Marc Roeder
##
## Invariants for partial difference sets
##
#H @(#)$Id: sigs.gi, v 1.6 2012/02/16 18:07:49 gap Exp $
##
#Y Copyright (C) 2006-2011 Marc Roeder
#Y
#Y This program is free software; you can redistribute it and/or
#Y modify it under the terms of the GNU General Public License
#Y as published by the Free Software Foundation; either version 2
#Y of the License, or (at your option) any later version.
#Y
#Y This program is distributed in the hope that it will be useful,
#Y but WITHOUT ANY WARRANTY; without even the implied warranty of
#Y MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
#Y GNU General Public License for more details.
#Y
#Y You should have received a copy of the GNU General Public License
#Y along with this program; if not, write to the Free Software
#Y Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
##
Revision.("sers/roeder/gap/pkg/rdsraw/rds/lib/sigs_gi"):=
"@(#)$Id: sigs.gi, v 1.6 2012/02/16 18:07:49 gap Exp $";
#############################################################################
##
#V MaxAutsizeForOrbitCalculation@
##
## In `ReducedStartsets', a bound is needed to decide if `Orbit' or
## `RepresentativeAction' should be used. If the group is larger than
## <MaxAutsizeForOrbitCalculation@RDS>, `RepresentativeAction' is used.
##
#BindGlobal("MaxAutsizeForOrbitCalculation@",5*10^6);
#InstallValue(MaxAutsizeForOrbitCalculation@,5*10^6);
#MaxAutsizeForOrbitCalculation@:=5*10^6;
#############################################################################
##
#O RDSFactorGroupData(<U>,<N>,<lambda>,<Gdata>);
##
InstallMethod(RDSFactorGroupData,
[IsGroup,IsObject,IsInt,IsRecord],
function(U,N,lambda,Gdata)
local group, cosets, csreps, cosetsperm, epi, fg, fglist,
intersectlist, returnlist;
group:=Gdata.G;
if not IsNormal(group,U)
then
Error("The normal subgroup should be a _normal_ subgroup");
fi;
cosets:=RightCosets(group,U);
csreps:=List(cosets,Representative);
cosetsperm:=List(cosets,coset->GroupList2PermList(Set(coset),Gdata));
epi:=NaturalHomomorphismByNormalSubgroup(group,U);
fg:=ImagesSource(epi);
fglist:=Set(fg);
intersectlist:=List(csreps,i->[Image(epi,i),Size(Intersection(RightCoset(U,i),N))]);
returnlist:=List(fglist,i->First(intersectlist,j->j[1]=i)[2]);
return rec(fg:=fg,
fglist:=fglist,
lambda:=lambda,
cosets:=cosetsperm,
cosetsreps:=csreps,
Usize:=Size(U),
fgaut:=AutomorphismGroup(fg),
Nfg:=Image(epi,N),
fgintersect:=intersectlist,
intersectshort:=returnlist);
end);
####### ####
##MatchingFGData: #
##Prueft, ob es in fgdatalist schon einen Eintrag gibt, die zum Datensatz
##fgmatchdata passt und gibt ihn zurueck.
##
## gibt es einen, ist er eindeutig, gibt es keinen, wird [] zurueckgegeben.
## Mindestgehalt von fgmatchdata:
## .fg, .Nfg .fgintersect .fgaut
## Dabei muss .Nfg eine Gruppe sein.
###### ####
InstallMethod(MatchingFGData,
[IsList,IsRecord],
function(fgdatalist,fgmatchdata)
local remaining,Nfgiso,fgiso,imageNfg,group,fgmatchset,fgmatchintnumbers,fggroupset,fggroupintnumbers,perm,Nfgaut,newfgiso, sigma;
if fgdatalist=[] then return [];fi;
remaining:=Filtered(fgdatalist,d->IsomorphismGroups(d.fg,fgmatchdata.fg)<>fail);
if remaining=[] then return fail;fi;
remaining:=Filtered(remaining,d->IsomorphismGroups(d.Nfg,fgmatchdata.Nfg)<>fail);
if remaining=[] then return fail;fi;
for group in remaining
do
fgiso:=IsomorphismGroups(fgmatchdata.fg,group.fg);
imageNfg:=Image(fgiso,fgmatchdata.Nfg);
if imageNfg=group.Nfg
then
fgmatchset:=List(fgmatchdata.fgintersect,i->i[1]);
fgmatchintnumbers:=List(fgmatchdata.fgintersect,i->i[2]);
fggroupset:=Set(group.fg);
fggroupintnumbers:=List(group.fgintersect,i->i[2]);
perm:=PermListList(Image(fgiso,fgmatchset),fggroupset);
if Permuted(fgmatchintnumbers,perm)=fggroupintnumbers
then
return group;
fi;
fi;
Nfgaut:=RepresentativeAction(group.fgaut,group.Nfg,imageNfg,OnSubgroups);
if Nfgaut<>fail
then
Info(DebugRDS,2,"*",Size(Stabilizer(group.fgaut,imageNfg,OnSubgroups)),"*\c");
for sigma in Stabilizer(group.fgaut,imageNfg,OnSubgroups) do
newfgiso:=fgiso*Nfgaut*sigma;
fgmatchset:=List(fgmatchdata.fgintersect,i->i[1]);
fgmatchintnumbers:=List(fgmatchdata.fgintersect,i->i[2]);
fggroupset:=List(group.fg);
fggroupintnumbers:=List(group.fgintersect,i->i[2]);
perm:=PermListList(Image(newfgiso,fgmatchset),fggroupset);
if Permuted(fgmatchintnumbers,perm)=fggroupintnumbers
then
return group;
fi;
od;
fi;
od;
return fail;
end);
####### ####
##MatchingFGDataNonGrp: #
##Prueft, ob es in fgdatalist schon einen Eintrag gibt, die zum Datensatz
##fgmatchdata passt und gibt ihn zurueck.
##
## gibt es einen, ist er eindeutig, gibt es keinen, wird [] zurueckgegeben.
## Mindestgehalt von fgmatchdata:
## .fg, .Nfg .fgintersect
## Hier muss .Nfg nicht Gruppe sein.
###### ####
InstallMethod(MatchingFGDataNonGrp,
[IsList,IsRecord],
function(fgdatalist,fgmatchdata)
local remaining,fgiso,Nfgiso,imageNfg,group,newfgiso,fgmatchset,fggroupset,fgmatchintnumbers,fggroupintnumbers,perm,Nfgaut,sigma ;
if fgdatalist=[] then return fail;fi;
remaining:=Filtered(fgdatalist,d->IsomorphismGroups(d.fg,fgmatchdata.fg)<>fail);
if remaining=[]
then
return fail;
fi;
for group in remaining
do
fgiso:=IsomorphismGroups(fgmatchdata.fg,group.fg);
imageNfg:=Image(fgiso,fgmatchdata.Nfg);
if imageNfg=group.Nfg
then
fgmatchset:=List(fgmatchdata.fgintersect,i->i[1]);
fgmatchintnumbers:=List(fgmatchdata.fgintersect,i->i[2]);
fggroupset:=List(group.fg);
fggroupintnumbers:=List(group.fgintersect,i->i[2]);
perm:=PermListList(Image(fgiso,fgmatchset),fggroupset);
if Permuted(fgmatchintnumbers,perm)=fggroupintnumbers
then
return group;
fi;
fi;
Nfgaut:=RepresentativeAction(group.fgaut,group.Nfg,imageNfg,OnSets);
if Nfgaut<>fail
then
Info(DebugRDS,2,"*",Size(Stabilizer(group.fgaut,imageNfg,OnSets)),"*\c");
for sigma in Stabilizer(group.fgaut,imageNfg,OnSets)
do
newfgiso:=fgiso*Nfgaut*sigma;
fgmatchset:=List(fgmatchdata.fgintersect,i->i[1]);
fgmatchintnumbers:=List(fgmatchdata.fgintersect,i->i[2]);
fggroupset:=List(group.fg);
fggroupintnumbers:=List(group.fgintersect,i->i[2]);
perm:=PermListList(Image(newfgiso,fgmatchset),fggroupset);
if Permuted(fgmatchintnumbers,perm)=fggroupintnumbers
then
return group;
fi;
od;
fi;
od;
return fail;
end);
#############################################################################
##
#O CosetSignatures( <Gsize>,<Usize>,<diffsetorder> ) calculates possible signatures for difference sets.
##
InstallMethod(CosetSignatures,[IsInt,IsInt,IsInt],
function(Gsize,Usize,diffsetorder)
local siglist, sig;
return CosetSignatures(Gsize,1,Usize,1,diffsetorder+1,1);
end);
#############################################################################
##
#O CosetSignatures( <Gsize>,<Nsize>,<Usize>,<Intersectsize>,<k>,<lambda>) calculates possible signatures for relative difference sets.
##
InstallMethod(CosetSignatures,[IsInt,IsInt,IsInt,IsInt,IsInt,IsInt],
function(Gsize,Nsize,Usize,Intersectsize,k,lambda) #order n=k-lambda
return CosetSignatures(Gsize,Nsize,Usize,[Intersectsize],k,lambda)[1][2];
end);
#############################################################################
##
#O CosetSignatures( <Gsize>,<Nsize>,<Usize>,<Intersectsizes>,<k>,<lambda>) calculates possible signatures for relative difference sets.
##
InstallMethod(CosetSignatures,[IsInt,IsInt,IsInt,IsDenseList,IsInt,IsInt],
function(Gsize,Nsize,Usize,Intersectsizes,k,lambda) #order n=k-lambda
local parameters, partint, range, partsize, sig,
sig0indices, largest, largestsquare, rightsides,
siglist, minright, maxright, sig0, leftside;
if Gsize<=Nsize then Error("Stupid parameters!");fi;
parameters:=[Gsize,Nsize,Usize,0,k,lambda];
partint:=k+Gsize/Usize;
range:=[1..k-lambda+1];
partsize:=Gsize/Usize;
sig:=[1..partsize];
sig0indices:=[2..partsize];
largest:=0;
largestsquare:=0;
rightsides:=List(Intersectsizes,i->k+lambda*(Usize-i));
siglist:=List(Intersectsizes,i->[[Gsize,Nsize,Usize,i,k,lambda],[]]);
minright:=Minimum(rightsides);
maxright:=Maximum(rightsides);
while range<>[]
do
largest:=range[Size(range)];
largestsquare:=(largest-1)^2;
sig[1]:=largest-1;
if largestsquare<=maxright and partint<=largest*partsize and largestsquare*partsize>=minright
then
for sig0 in RestrictedPartitions(partint-largest,range,partsize-1)
do
Apply(sig0,i->i-1);
leftside:=largestsquare+sig0*sig0;
if leftside in rightsides
then
sig{sig0indices}:=sig0;
AddSet(siglist[Position(rightsides,leftside)][2],SortedList(sig));
fi;
od;
fi;
Unbind(range[Size(range)]);
od;
return siglist;
end);
#############################################################################
##
#O TestedSignatures(<sigs>,<group>,<normalsg>[,<maxtest>][,<moretest>]) returns a subset of <sigs> satisfying necessary conditions.
##
InstallMethod(TestedSignatures,
[IsList,IsGroup,IsGroup],
function(sigs,group,normalsg)
return TestedSignatures(sigs,group,normalsg,0,true);
end);
InstallMethod(TestedSignatures,
[IsList,IsGroup,IsGroup,IsInt],
function(sigs,group,normalsg,maxtest)
return TestedSignatures(sigs,group,normalsg,maxtest,true);
end);
InstallMethod(TestedSignatures,
[IsList,IsGroup,IsGroup,IsBool],
function(sigs,group,normalsg,moretest)
return TestedSignatures(sigs,group,normalsg,0,moretest);
end);
InstallMethod(TestedSignatures,
[IsList,IsGroup,IsGroup,IsInt,IsBool],
function(sigs,group,normalsg,maxtest,moretest)
local Nsize, lsigs, factorgrp, sig;
Nsize:=Size(normalsg);
lsigs:=[];
if Size(sigs)=1 and not moretest
then
Info(InfoRDS,1,"There is only one signature to test, I will skip it as requested:\n",sigs[1]);
return sigs;
fi;
factorgrp:=FactorGroup(group,normalsg);
if IsCyclic(factorgrp)
then
for sig in sigs
do
if maxtest<>0 and NrPermutationsList(sig)>maxtest
then
Add(lsigs,sig);
Info(InfoRDS,2,"Signature ",sig," has too many permutations, not tested as requested. factor:",Int(NrPermutationsList(sig)/maxtest));
elif Position(sigs,sig)=Size(sigs) and lsigs=[] and not moretest
then
Info(InfoRDS,1,"All but the last signature died. Adding it without testing");
Add(lsigs,sig);
elif TestSignatureCyclicFactorGroup(sig,Nsize)
then
Add(lsigs,sig);
fi;
od;
else
for sig in sigs
do
if maxtest<>0 and NrPermutationsList(sig)>maxtest
then
Add(lsigs,sig);
Info(InfoRDS,2,"Signature ",sig," has too many permutations, not tested as requested, factor:",Int(NrPermutationsList(sig)/maxtest));
elif Position(sigs,sig)=Size(sigs) and lsigs=[] and not moretest
then
Info(InfoRDS,1,"All but the last signature died. Adding it without testing");
Add(lsigs,sig);
elif TestSignatureLargeIndex(sig,group,normalsg,factorgrp)
then
Add(lsigs,sig);
fi;
od;
fi;
return lsigs;
end);
#############################################################################
##
#O TestSignatureLargeIndex(<sig>,<group>,<Normalsg>) tests if a given list can be signature for a difference set
##
InstallMethod(TestSignatureLargeIndex,
[IsList,IsGroup,IsGroup],
function(sig,group,Normalsg)
local factorgrp;
factorgrp:=FactorGroup(group,Normalsg);
return TestSignatureLargeIndex(sig,group,Normalsg,factorgrp);
end);
#############################################################################
##
#O TestSignatureLargeIndex(<sig>,<group>,<Normalsg>,<factorgrp>) tests if a given list can be signature for a difference set
##
InstallMethod(TestSignatureLargeIndex,
[IsList,IsGroup,IsGroup,IsGroup],
function(sig,group,Normalsg,factorgrp)
local fgrplist, nsgsize, offs, partitions, part, perma,
permb, parta, partb, psig;
fgrplist:=Set(factorgrp); #Faktorgruppe als strikt geordnete Liste
nsgsize:=Size(Normalsg);
offs:=Filtered(fgrplist,i->Order(i)<>1); #offset.
partitions:=List(Combinations(sig,Int(Size(sig)/2)),i->[i,RemovedSublist(sig,i)]);
for part in partitions #Alle Permutationen von sig zu berechnen ist zu
do # speicheraufwaendig. Teile sig also in zwei Teile
perma:=Iterator(PermutationsList(part[1])); # und rechne die Permutationen so in Stuecken.
permb:=PermutationsList(part[2]);
for parta in perma
do
for partb in permb
do
psig:=Concatenation(parta,partb);
if ForAll(offs,o->Sum(fgrplist,i->(psig[PositionSet(fgrplist,i)]*psig[PositionSet(fgrplist,(i*o))]))=nsgsize)
then
return true;
fi;
od;
od;
od;
return false;
end);
#############################################################################
##
#O TestSignatureCyclicFactorGroup(<sig>,<Nsize>) tests if a list can be signature for a difference set
##
InstallMethod(TestSignatureCyclicFactorGroup,
[IsList,IsInt],
function(sig,Nsize)
local index, indices, offs, partitions, part, perma,
permb, parta, partb, psig;
index:=Size(sig);
indices:=[0..index-1];
offs:=Filtered(indices,i->(i mod index <>0));
partitions:=List(Combinations(sig,Int(index/2)),i->[i,RemovedSublist(sig,i)]);
for part in partitions
do
perma:=Iterator(PermutationsList(part[1]));
permb:=PermutationsList(part[2]);
for parta in perma
do
for partb in permb
do
psig:=Concatenation(parta,partb);
if ForAll(offs,o->Sum(indices,i->(psig[i+1]*psig[((i-o) mod index)+1]))=Nsize)
then # Size(psig)=Size(sig)=|G:N|
return true;
fi;
od;
od;
od;
return false;
end);
#############################################################################
#O TestSignatureRelative(<sig>,<fgdata>) tests if a list can be signature for a relative difference set with forbidden set
##
InstallMethod(TestSignatureRelative,
[IsList,IsRecord],
function(sig,fgdata)
local Intersectsize, fgrplist, Usize, lambda, offsnonN,
offsN, partitions, part, perma, permb, parta, partb,
psig, intersectlist;
if Size(Set(fgdata.fgintersect))=1
then
Intersectsize:=Set(fgdata.fgintersect);
else
Intersectsize:=0;
fi;
##
# U=N is the trivial case #
##
if Intersectsize>0 and fgdata.Usize=Intersectsize and Size(fgdata.Nfg)=1
then
if Number(sig,i->i=1)=Sum(sig) then return true; else return false;fi;
fi;
if not Size(fgdata.fg)=Size(sig)
then
Error("fg and sig don't match");
fi;
fgrplist:=fgdata.fglist;
Usize:=fgdata.Usize;
lambda:=fgdata.lambda;
offsnonN:=Set(Filtered(fgrplist,i->Order(i)<>1)); #offset.
offsN:=Filtered(IntersectionSet(fgrplist,Set(fgdata.Nfg)),i->Order(i)<>1); #offset in Nfg
SubtractSet(offsnonN,offsN); #offset outside Nfg
partitions:=List(Combinations(sig,Int(Size(sig)/2)),i->[i,RemovedSublist(sig,i)]);
if Intersectsize>0
then
for part in partitions
do
perma:=Iterator(PermutationsList(part[1]));
permb:=PermutationsList(part[2]);
for parta in perma
do
for partb in permb
do
psig:=Concatenation(parta,partb);
if ForAll(offsN,o->Sum(fgrplist,i->(psig[PositionSet(fgrplist,i)]*psig[PositionSet(fgrplist,(i*o))]))=lambda*(Usize-Intersectsize))
and
ForAll(offsnonN,o->Sum(fgrplist,i->(psig[PositionSet(fgrplist,i)]*psig[PositionSet(fgrplist,(i*o))]))=lambda*Usize)
then
return true;
fi;
od;
od;
od;
else
intersectlist:=fgdata.intersectshort;
for part in partitions
do
perma:=Iterator(PermutationsList(part[1]));
permb:=PermutationsList(part[2]);
for parta in perma
do
for partb in permb
do
psig:=Concatenation(parta,partb);
if ForAll(offsN,o->Sum(fgrplist,i->(psig[PositionSet(fgrplist,i)]*psig[PositionSet(fgrplist,(i*o))]))=lambda*(Usize-intersectlist[PositionSet(fgrplist,o)]))
and
ForAll(offsnonN,o->Sum(fgrplist,i->(psig[PositionSet(fgrplist,i)]*psig[PositionSet(fgrplist,(i*o))]))=lambda*Usize)
then
return true;
fi;
od;
od;
od;
fi;
return false;
end);
#############################################################################
##
#O TestedSignaturesRelative(<sigs>,<fgdata>,[,<maxtest>][,<moretest>]) returns subset of <sigs> which might be a set of signatures of relative difference sets with forbidden group.
##
InstallMethod(TestedSignaturesRelative,
[IsList,IsRecord,IsInt],
function(sigs,fgdata,maxtest)
return TestedSignaturesRelative(sigs,fgdata,maxtest,true);
end);
InstallMethod(TestedSignaturesRelative,
[IsList,IsRecord],
function(sigs,fgdata)
return TestedSignaturesRelative(sigs,fgdata,0,true);
end);
InstallMethod(TestedSignaturesRelative,
[IsList,IsRecord,IsBool],
function(sigs,fgdata,moretest)
return TestedSignaturesRelative(sigs,fgdata,0,moretest);
end);
InstallMethod(TestedSignaturesRelative,
[IsList,IsRecord,IsInt,IsBool],
function(sigs,fgdata,maxtest,moretest)
local lsigs, sig;
lsigs:=[];
if Size(sigs)=1 and not moretest
then
Info(InfoRDS,1,"All but the last signature died. Adding it without testing");
return sigs;
fi;
for sig in sigs
do
if maxtest<>0 and NrPermutationsList(sig)>maxtest
then
Add(lsigs,sig);
Info(InfoRDS,2,"Signature ",sig," has too many permutations, I didn't test it. Factor: ",Int(NrPermutationsList(sig)/maxtest));
elif Position(sigs,sig)=Size(sigs) and lsigs=[] and not moretest
then
Info(InfoRDS,1,"All but the last signature died. Adding it without testing");
Add(lsigs,sig);
elif TestSignatureRelative(sig,fgdata)
then
Add(lsigs,sig);
fi;
od;
return lsigs;
end);
#############################################################################
##
#F OrderedCosetSignatureOfSet( <set>,<cosets>) calculate the signature of a patial RDS.
##
InstallGlobalFunction("OrderedCosetSignatureOfSet",
function(set,cosets)
local sig, class;
sig:=[];
for class in cosets
do
Add(sig,Number(set,i->i in class));
od;
return sig;
end);
#############################################################################
##
#F CosetSignatureOfSet( <set>,<cosets>) calculate the signature of a patial RDS.
##
InstallGlobalFunction("CosetSignatureOfSet",
function(set,cosets)
return SortedList(OrderedCosetSignatureOfSet(set,cosets));
end);
#############################################################################
##
#O SigInvariant( < prd >,<data>) calculates the signature of a partial relative difference set.
##
InstallMethod(SigInvariant,
[IsDenseList,IsDenseList],
function(set,cosets_sigs)
local lset,coset_data,setsig,return_list;
if cosets_sigs=[]
then
return [];
fi;
if IsListOfIntegers(set) or not (IsSet(set) and
CategoryCollections(IS_REC)(cosets_sigs))
then
TryNextMethod();
fi;
if not set[1]^0 in set
then
lset:=Union(set,[set[1]^0]);
else
lset:=set;
fi;
return_list:=[];
for coset_data in cosets_sigs
do
setsig:=CosetSignatureOfSet(lset,coset_data.cosets);
if ForAll(coset_data.sigs,i->(not Pointwiseleq(setsig,i)))
then
return fail;
else
Add(return_list,setsig);
fi;
od;
return_list:=Collected(return_list);
return return_list;
end);
##########
InstallOtherMethod(SigInvariant,
[IsDenseList,IsDenseList],
function(set,cosets_sigs)
local lset,coset_data,setsig,return_list;
if cosets_sigs=[]
then
return [];
fi;
if not IsListOfIntegers(set) or not (IsSet(set) and
CategoryCollections(IS_REC)(cosets_sigs))
then
TryNextMethod();
fi;
if not 1 in set
then
lset:=Union(set,[1]);
else
lset:=set;
fi;
return_list:=[];
for coset_data in cosets_sigs
do
setsig:=CosetSignatureOfSet(lset,coset_data.cosets);
if ForAll(coset_data.sigs,i->(not Pointwiseleq(setsig,i)))
then
return fail;
else
Add(return_list,setsig);
fi;
od;
return_list:=Collected(return_list);
return return_list;
end);
#############################################################################
##
#O ReducedStartsets(<startsets>,<autlist>,<csdata>,<difftable>) returns a reduced set of startsets
##
InstallMethod(ReducedStartsets,
"for partial relative difference sets",
[IsDenseList,IsDenseList,IsDenseList,IsMatrix],
function(startsets,autlist,csdata,difftable)
return ReducedStartsets(startsets,autlist,s->SigInvariant(Union(s,[1]),csdata),difftable);
end);
#
# rewritten (just after version 1.0) and moved to separate file:
#
##############################################################################
###
##O ReducedStartsets(<startsets>,<autlist>,<func>,<difftable>) returns a reduced set of startsets
###
#InstallMethod(ReducedStartsets,
# "for partial relative difference sets",
# [IsDenseList,IsDenseList,IsFunction,IsMatrix],
# function(startsets,autlist,func,difftable)
# local Translates, timetmp, partition, returnset, lssets,
# transset, auts, set, interesting_sets, orbit,
# interesting, transset_pos;
#
# if not IsSet(startsets) then Error("\nThe set of startsets must be a SET\n");fi;
# Info(InfoRDS,1,"Size ",Size(startsets));
# if startsets=[] then return [];fi;
#
# Translates:=function(set)
# local returnlist, g, trans;
#
# returnlist:=[];
# for g in set
# do
# trans:=difftable{set}[g];
# Add(trans,difftable[1][g]);
# Sort(trans);
# RemoveSet(trans,1);
# Add(returnlist,trans);
# od;
# Add(returnlist,AsSet(set));
# return returnlist;
# end;
# timetmp:=Runtime();
# partition:=PartitionByFunction(startsets,func);
# Info(InfoRDS,1,Size(partition),"/ ",Number(partition,p->Size(p)=1)," @",StringTime(Runtime()-timetmp));
# Apply(partition,SortedList);
#
# returnset:=[];
# for lssets in partition
# do
# Info(DebugRDS,2,Size(lssets));
# if Size(lssets)>1
# then
# transset:=Set(lssets,l->[l,Translates(l)]);#Translatmengen
# for auts in autlist
# do
# for set in lssets
# do
# if Size(set)>1 and Size(auts)>MaxAutsizeForOrbitCalculation
# then
# interesting_sets:=Set(Filtered(transset,t->ForAny(t[2],s->RepresentativeAction(auts,s,AsSet(set),OnSets)<>fail)),
# i->i[1]);
# else
# orbit:=AsSortedList(Orbit(auts,AsSet(set),OnSets));;
# interesting_sets:=Set(Filtered(transset,t->ForAny(t[2],s->s in orbit)),
# i->i[1]);
# fi;
# interesting_sets:=Intersection(interesting_sets,lssets);
# RemoveSet(interesting_sets,Reversed(Minimum(List(interesting_sets,b->Reversed(b)))));
# for interesting in interesting_sets
# do
# Unbind(lssets[Position(lssets,interesting)]);
# for transset_pos in [1..Size(transset)]
# do
# if IsBound(transset[transset_pos])
# and transset[transset_pos][1]=interesting
# then
# Unbind(transset[transset_pos]);
# break;
# fi;
# od;
# od;
# # if not set in lssets then Error("PANIC! this should not happen!");fi;
# od; #<for set in lssets>
# Info(DebugRDS,2,"->",Size(Compacted(lssets)));
# od;
# fi; #<\if Size(lssets)>1>#
# od; #<\for lssets in partition>#
# returnset:=Compacted(Concatenation(partition));
# return SortedList(returnset);
#end);
#
#InstallMethod(ReducedStartsets,
# "for partial relative difference sets",
# [IsDenseList,IsDenseList,IsDenseList,IsRecord],
# function(startsets,autlist,csdata,data)
# return ReducedStartsets(startsets,autlist,csdata,data.diffTable);
#end);
#
#InstallMethod(ReducedStartsets,
# "for partial relative difference sets",
# [IsDenseList,IsDenseList,IsFunction,IsRecord],
# function(startsets,autlist,func,data)
# return ReducedStartsets(startsets,autlist,func,data.diffTable);
#end);
#############################################################################
##
#O SignatureDataForNormalSubgroups(<Normals>,<globalSigData>,<forbiddenSet>,<Gdata>,<parameters>)
##
InstallMethod(SignatureDataForNormalSubgroups,
[IsDenseList,IsList,IsObject,IsRecord,IsDenseList],
function(Normals,globalSigData,forbiddenSet,Gdata,parameters)
local k, lambda, maxtest, moretest, forbidden, isgroup,
groupOrder, forbiddenSetOrder, normalSubgroupsData,
isbadforbiddenset, nsg, Usize, Intersectsize,
csparameters, oldfgsigs, sigs, olddata, newdata,
newglobaldata, fgmatch, cosets;
k:=parameters[1];
lambda:=parameters[2];
maxtest:=parameters[3];
moretest:=parameters[4];
if not IsSubset(Gdata.G,Set(forbiddenSet))
then
Error("forbidden set must be a list of group elements or a group");
fi;
if IsGroup(forbiddenSet)
then
forbidden:=forbiddenSet;
isgroup:=true;
elif Size(Group(forbiddenSet))=Size(forbiddenSet)
then
isgroup:=true;
forbidden:=Group(forbiddenSet);
else
isgroup:=false;
forbidden:=forbiddenSet;
fi;
if not IsInt(k) and IsInt(lambda) and IsInt(maxtest) and IsBool(moretest)
then
Error("wrong parameters");
fi;
groupOrder:=Size(Gdata.G);
forbiddenSetOrder:=Size(forbidden);
normalSubgroupsData:=[];
isbadforbiddenset:=false;
for nsg in Filtered(Normals,n->not (Size(n)=1 or n=Gdata.G))
do
if not isbadforbiddenset
then
Usize:=Size(nsg);
Intersectsize:=Size(Intersection(forbidden,nsg));
csparameters:=[groupOrder,forbiddenSetOrder,Usize,Intersectsize,k,lambda];
oldfgsigs:=[];
sigs:=[];
####look if this has already been calculated...####
if IsBound(globalSigData[Usize]) and globalSigData[Usize]<>[]
then
olddata:=Filtered(globalSigData[Usize],d->d.cspara=csparameters);
else
olddata:=[];
fi;
if olddata<>[]
then
if Size(olddata)>1
then
Error("global signature data is corrupt!");
fi;
olddata:=olddata[1]; #olddata has just one entry.
sigs:=olddata.sigs;
oldfgsigs:=olddata.fgsigs;
else ####...if not, calculate it now.
sigs:=CallFuncList(CosetSignatures,csparameters);
fi;
newdata:=RDSFactorGroupData(nsg,forbidden,lambda,Gdata);
newdata.sigs:=StructuralCopy(sigs);
newglobaldata:=rec(cspara:=csparameters,sigs:=sigs,fgsigs:=[newdata]);
if newglobaldata.fgsigs[1].sigs=[]
then
Info(InfoRDS,1,"Signature equations have no solution.");
isbadforbiddenset:=true;#this forbidden group does not occur
return fail; # nothing to to here...
fi;
fgmatch:=fail;
if oldfgsigs<>[]
then
if not isgroup
then
fgmatch:=MatchingFGDataNonGrp(oldfgsigs,newglobaldata.fgsigs[1]);
else
fgmatch:=MatchingFGData(oldfgsigs,newglobaldata.fgsigs[1]);
fi;
fi;
if fgmatch=fail
### ###
# oldfgsigs=[] means, csparameters has not been calculated before#
# fgmatch=fail means, the factor groups do not match any of the #
# previous ones #
### ###
then
newglobaldata.fgsigs[1].sigs:=TestedSignaturesRelative(sigs,newdata,maxtest,moretest);
newdata.sigs:=newglobaldata.fgsigs[1].sigs; #for this run
if newglobaldata.fgsigs[1].sigs=[]
then
Info(InfoRDS,1,"Signature equations have no solution.");
isbadforbiddenset:=true;
fi;
if oldfgsigs<>[]
then
Append(oldfgsigs,newglobaldata.fgsigs); #Pointers! Beware!
else
if IsBound(globalSigData[Usize])
then
Add(globalSigData[Usize],newglobaldata);
else
globalSigData[Usize]:=[newglobaldata];
fi;
fi;
else #old data can be used. I saved some work!
newdata.sigs:=fgmatch.sigs;
fi;
Add(normalSubgroupsData,
rec(subgroup:=nsg,
sigs:=newdata.sigs,
cosets:=newdata.cosets,
#cosetsgroup:=newdata.cosetsgroup
)
); #data for this time.
fi;
od;
if isbadforbiddenset
then
return fail;
else
return normalSubgroupsData;
fi;
end);
#############################################################################
##
## Here are some methods for ordered signatures from quotient images
##
#############################################################################
#############################################################################
##
#O MultiplicityInvariantLargeLambda( <set>,<Gdata>)
##
InstallMethod(MultiplicityInvariantLargeLambda,
[IsDenseList,IsRecord],
function(set,Gdata)
local mults;
mults:=List(Collected(AllPresentables(set,Gdata)),i->i[2]);
return Collected(mults);
end);
#############################################################################
##
#O NormalSgsForQuotientImages(<forbidden>,<Gdata>)
##
InstallMethod(NormalSgsForQuotientImages,
[IsMagmaWithInverses,IsRecord],
function(forbidden,Gdata)
local normals, list;
normals:=Filtered(NormalSubgroups(Gdata.G),n->IsSubgroup(forbidden,n)
and not Order(n)=1
and not n=forbidden);
list:=PartitionByFunction(normals,n->IdSmallGroup(FactorGroup(Gdata.G,n)));
return Set(list,Representative);
end);
InstallMethod(NormalSgsForQuotientImages,
[IsDenseList,IsRecord],
function(forbidden,Gdata)
local forb, normals, list;
if IsListOfIntegers(forbidden)
then
forb:=PermList2GroupList(forbidden,Gdata);
else
forb:=forbidden;
fi;
normals:=Filtered(NormalSubgroups(Gdata.G),n->IsSubset(forb,n)
and not Order(n)=1
and not Size(n)=Size(forb));
list:=PartitionByFunction(normals,n->IdSmallGroup(FactorGroup(Gdata.G,n)));
return Set(list,Representative);
end);
#############################################################################
##
#O DataForQuotientImage(<normal>,<forbidden>,<k>,<lambda>,<Gdata>);
##
InstallMethod(DataForQuotientImage,
[IsMagmaWithInverses,IsMagmaWithInverses,IsPosInt,IsPosInt,IsRecord],
function(normal,forbidden,k,lambda,Gdata)
return DataForQuotientImage(normal,Set(forbidden),k,lambda,Gdata);
end);
InstallMethod(DataForQuotientImage,
[IsMagmaWithInverses,IsDenseList,IsPosInt,IsPosInt,IsRecord],
function(normal,forbidden,k,lambda,Gdata)
local forb, phi, cosets, fGroup, auts, fauts, fGroupData,
fforbidden, flambda;
if not IsSubgroup(Gdata.G,normal) or not IsNormal(Gdata.G,normal)
then
Error("`normal' must be a normal subgroup ");
fi;
if IsListOfIntegers(forbidden)
then
forb:=PermList2GroupList(forbidden,Gdata);
else
forb:=forbidden;
fi;
if not IsSubset(forb,normal)
then
Error("normal subgroup must lie in the forbidden set");
fi;
phi:=NaturalHomomorphismByNormalSubgroup(Gdata.G,normal);
cosets:=PartitionByFunction(Gdata.Glist,x->x^phi);
# represent cosets by lists of integers:
Apply(cosets,i->Set(GroupList2PermList(i,Gdata)));
fGroup:=ImagesSource(phi);
auts:=Intersection(Stabilizer(Gdata.A,Set(normal),OnSets),
Stabilizer(Gdata.A,Set(forb),OnSets));
fauts:=Group(Set(GeneratorsOfGroup(auts),g->g^phi));
fGroupData:=PermutationRepForDiffsetCalculations(fGroup,fauts);;
fforbidden:=Image(phi,forb);
flambda:=Order(normal)*lambda;
return rec(Gdata:=fGroupData,forbidden:=fforbidden,lambda:=flambda);
end);
#############################################################################
##
#O OrderedSigsFromQuotientImages(<fGroupData>,<qimages>,<forbidden>,<normal>,<Gdata>)
##
InstallMethod(OrderedSigsFromQuotientImages,
[IsRecord,IsDenseList,IsObject,IsMagmaWithInverses,IsRecord],
function(fGroupData,qimages,forbidden,normal,Gdata)
local fforbiddens, fforbidden, fAut, epi, fgroup, iso,
phi, forbiddenimage, psi, phi2, sigs, pos, set, i,
cosets, cosetsindices, unsortingPerm;
if not IsSubgroup(Gdata.G,normal)
then
Error("`normal' must be a normal subgroup of `Gdata'");
fi;
# calculate the forbidden set in the factor group:
fforbiddens:=Set(qimages,i->Set(Difference([2..Size(fGroupData.Glist)],AllPresentables(i,fGroupData))));
if not Size(fforbiddens)=1
then
Error("`qimages' have different forbidden sets!");
else
fforbidden:=PermList2GroupList(Union([1],fforbiddens[1]),fGroupData);
if Size(Group(fforbidden))=Size(fforbidden)
then
fforbidden:=Group(fforbidden);
else
fforbidden:=Set(fforbidden);
fi;
fi;
fAut:=AutomorphismGroup(fGroupData.G);
epi:=NaturalHomomorphismByNormalSubgroup(Gdata.G,normal);
fgroup:=ImagesSource(epi);
iso:=IsomorphismGroups(fgroup,fGroupData.G);
if iso<>fail
then
phi:=epi*iso;
if IsGroup(normal)
then
forbiddenimage:=Image(phi,forbidden);
else
forbiddenimage:=Set(Image(phi,Set(forbidden)));
fi;
if not forbiddenimage=fforbidden
then
if IsGroup(normal)
then
psi:=RepresentativeAction(fAut,forbiddenimage,fforbidden,OnSubgroups);
else
psi:=RepresentativeAction(fAut,forbiddenimage,fforbidden,OnSets);
fi;
else
psi:=phi;
fi;
if psi=fail
then
Error("forbidden set does not match!");
elif psi<>phi
then
phi2:=phi*psi;
else
phi2:=phi;
fi;
else
Error("normal subgroup does not match!");
fi;
sigs:=List(qimages,i->ListWithIdenticalEntries(Size(fGroupData.Glist),0));
for pos in [1..Size(qimages)]
do
set:=Union(qimages[pos],[1]);
for i in set
do
sigs[pos][i]:=sigs[pos][i]+1;
od;
od;
cosets:=PartitionByFunction([1..Size(Gdata.Glist)],i->PositionSet(fGroupData.Glist,Gdata.Glist[i]^phi2));
Apply(cosets,Set);
Sort(cosets);
# if the cosets are not ordered in the same way as the elements of
# the factor group, we will have to permute the ordered signatures.
# So now we claculate the according permutation (in most cases, this
# will be the trivial one)
cosetsindices:=List(cosets,i->PositionSet(fGroupData.Glist,(PermList2GroupList([i[1]],Gdata)[1])^phi2));
unsortingPerm:=Inverse(SortingPerm(cosetsindices));
# Sort the signatures according to the order of cosets:
Apply(sigs,s->Permuted(s,unsortingPerm));
return rec(orderedSigs:=sigs,cosets:=cosets,fg:=fGroupData.G,fgaut:=fAut,Nfg:=fforbidden);
end);
#############################################################################
##
#O OrderedSigInvariant( < prd >,<data>) calculates the signature of a partial relative difference set.
##
InstallMethod(OrderedSigInvariant,
[IsDenseList,IsDenseList],
function(set,cosets_sigs)
local lset, return_list, coset_data, setsig;
if cosets_sigs=[]
then
return [];
fi;
if IsListOfIntegers(set) or not (IsSet(set) and
CategoryCollections(IS_REC)(cosets_sigs))
then
TryNextMethod();
fi;
if not set[1]^0 in set
then
lset:=Union(set,[set[1]^0]);
else
lset:=set;
fi;
return_list:=[];
for coset_data in cosets_sigs
do
setsig:=OrderedCosetSignatureOfSet(lset,coset_data.cosets);
if ForAll(coset_data.orderedSigs,i->(not Pointwiseleq(setsig,i)))
then
return fail;
else
Add(return_list,setsig);
fi;
od;
return_list:=Collected(return_list);
return return_list;
end);
##########
InstallOtherMethod(OrderedSigInvariant,
[IsDenseList,IsDenseList],
function(set,cosets_sigs)
local lset,coset_data,setsig,return_list;
if cosets_sigs=[]
then
return [];
fi;
if not IsListOfIntegers(set) or not (IsSet(set) and
CategoryCollections(IS_REC)(cosets_sigs))
then
TryNextMethod();
fi;
if not 1 in set
then
lset:=Union(set,[1]);
else
lset:=set;
fi;
return_list:=[];
for coset_data in cosets_sigs
do
setsig:=OrderedCosetSignatureOfSet(lset,coset_data.cosets);
if ForAll(coset_data.orderedSigs,i->(not Pointwiseleq(setsig,i)))
then
return fail;
else
Add(return_list,setsig);
fi;
od;
return_list:=Collected(return_list);
return return_list;
end);
#############################################################################
##
#O MatchingFGDataForOrderedSigs(<forbidden>,<group>,<normalsgs>,<fgdata>)
##
InstallOtherMethod(MatchingFGDataForOrderedSigs,
[IsObject,IsRecord,IsDenseList,IsDenseList],
function(forbidden,Gdata,normalsgs,fgdata)
local forb;
if IsListOfIntegers(forbidden)
then
forb:=PermList2GroupList(forbidden,Gdata);
fi;
if not IsSubset(Gdata.Glist,forb)
then
Error("forbidden set must be in <Gdata.Glist>");
fi;
return MatchingFGDataForOrderedSigs(forb,Gdata,normalsgs,fgdata);
end);
#############################################################################
##
#O MatchingFGDataForOrderedSigs(<forbidden>,<group>,<normalsgs>,<fgdata>)
##
InstallMethod(MatchingFGDataForOrderedSigs,
[IsObject,IsRecord,IsDenseList,IsDenseList],
function(forbidden,Gdata,normalsgs,fgdata)
local group, isgroup, returnlist, forb, normal, phi,
quotient, quotid, filteredfgdata, fg, psi, forbimage,
rho;
group:=Gdata.G;
isgroup:=false;
returnlist:=[];
if IsGroup(forbidden)
then
forb:=forbidden;
isgroup:=true;
elif IsDenseList(forbidden) and Size(Group(forbidden))=Size(forbidden)
then
forb:=Group(forbidden);
isgroup:=true;
elif IsDenseList(forbidden) and IsListOfIntegers(forbidden)
then
TryNextMethod();
elif IsDenseList(forbidden) and IsSubset(Gdata.Glist,forbidden)
then
forb:=forbidden;
isgroup:=false;
else
Error("forbidden set is not valid");
fi;
for normal in normalsgs
do
phi:=NaturalHomomorphismByNormalSubgroup(group,normal);
quotient:=ImagesSource(phi);
quotid:=IdSmallGroup(quotient);
filteredfgdata:=Filtered(fgdata,i->IdSmallGroup(i.fg)=quotid);
for fg in filteredfgdata
do
psi:=IsomorphismGroups(quotient,fg.fg);
if isgroup
then
forbimage:=Image(phi*psi,forb);
else
forbimage:=Set(Image(phi*psi,forb));
fi;
if forbimage=fg.Nfg
then
Add(returnlist,rec(nomral:=normal,hom:=phi*psi,sigdata:=fg));
else
if isgroup
then
rho:=RepresentativeAction(fg.fgaut,forbimage,fg.Nfg,OnSubgroups);
else
rho:=RepresentativeAction(fg.fgaut,forbimage,fg.Nfg,OnSets);
fi;
if rho<>fail
then
Add(returnlist,rec(normal:=normal,hom:=phi*psi*rho,sigdata:=fg));
fi;
fi;
od;
od;
return returnlist;
end);
#############################################################################
##
#E ........ ENDE
##