GAP 4.8.9 installation with standard packages -- copy to your CoCalc project to get it
#############################################################################
##
#W reps.gi RDS Package Marc Roeder
##
## Representation theoretic methods for a special class of groups and difference sets
##
#H @(#)$Id: reps.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/reps_gi"):=
"@(#)$Id: reps.gi, v 1.6 2012/02/16 18:07:49 gap Exp $";
SetInfoLevel(InfoRDS,1);
SetInfoLevel(DebugRDS,0);
#############################################################################
##
#P IsListOfIntegers( <list> ) test if a collection contains only integers.
##
InstallMethod(IsListOfIntegers,"for lists",
[IsDenseList],x->IsSubset(Integers,x)
);
InstallOtherMethod(IsListOfIntegers,"for lists",
[IsObject],
function(x)
if IsDenseList(x)
then
TryNextMethod();
else
return false;
fi;
end);
#############################################################################
##
#P IsRootOfUnity( <cyc> ) test if a cyclotomic is a root of unity.
##
InstallMethod(IsRootOfUnity,"for cyclotomics",
[IsCyclotomic],x->x*ComplexConjugate(x)=1
);
#############################################################################
##
#O CoeffList2CyclotomicList( <list>,<root> ) takes a list of integers and returns a list of integral cyclotomics.
##
InstallMethod(CoeffList2CyclotomicList,
"for lists of integers and roots of unity",
[IsSmallList,IsCyc],
function(list,root)
if not IsRootOfUnity(root) or not IsListOfIntegers(list)
then
TryNextMethod();
fi;
return List([1..Size(list)],i->list[i]*root^(i-1));
end);
RedispatchOnCondition(CoeffList2CyclotomicList,
true,
[IsList,IsCyc],[IsList,IsIntegralCyclotomic],0
);
#############################################################################
##
#O AbssquareInCyclotomics( <list>,<root> ) returns the modulus of an algebraic integer given by <list> and <root>.
##
InstallMethod(AbssquareInCyclotomics,
"for lists of integers and roots of unity",
[IsSmallList,IsCyc],
function(list,root)
local list1,sum1;
if not IsRootOfUnity(root) or not IsListOfIntegers(list)
then
TryNextMethod();
fi;
list1:=CoeffList2CyclotomicList(list,root);
sum1:=Sum(list1);
return sum1*ComplexConjugate(sum1);
end);
#############################################################################
##
#O List2Tuples( <list>,<int> ) splits <list> into <int> parts
##
InstallMethod(List2Tuples,"for lists",
[IsList,IsPosInt],
function(list,parts)
local partlength, tmplist;
if not Size(list) mod parts =0
then
Error("Size of <list> must be divisible by <parts>");
fi;
partlength:=Size(list) / parts;
tmplist:=[1..partlength];
return List([0..parts-1],i->list{i*partlength+tmplist});
end);
#############################################################################
##
#O CycsGivenCoeffSum( <sum>, <root> ) returns all cyclotomic integers with given coefficient sum.
##
InstallMethod(CycsGivenCoeffSum,"for cyclotomic integers",
[IsCyc,IsCyc],
function(sum,root)
local rorder, partitions, returnlist;
if not IsRootOfUnity(root) then TryNextMethod();fi;
rorder:=Order(root);
partitions:=OrderedPartitions(sum+rorder,rorder);
Apply(partitions,i->i-1);
returnlist:=PartitionByFunctionNF(partitions,i->
AbssquareInCyclotomics(i,root));
return List(returnlist,i->[AbssquareInCyclotomics(Representative(i),root),i]);
end);
#############################################################################
##
#O NormalSubgroupsForRep
##
InstallMethod(NormalSubgroupsForRep,
[IsRecord,IsInt],
function(Gdata,divisor)
local group, returnlist, normals, Nsg, epi, fgrp, gens,
b, a, rootorder, m, fgrp2pairmap, int2Gmap, root,
int2pairtable;
group:=Gdata.G;
returnlist:=[];
normals:=Set(Filtered(NormalSubgroups(group),i->
(Index(group,i) mod divisor=0)
and not Size(i)=Size(group) and not Size(i)=1
and not Index(group,i)=divisor)
);
normals:=Filtered(normals,i->not IsAbelian(FactorGroup(group,i)));
for Nsg in normals
do
epi:=NaturalHomomorphismByNormalSubgroup(group,Nsg);
fgrp:=ImagesSource(epi);
fgrp:=FactorGroup(group,Nsg);
gens:=MinimalGeneratingSet(fgrp);
b:=First(gens,i->Order(i)=divisor);
a:=First(gens,i->Order(i)<>divisor);
if Size(gens)=2 and b<>fail and (a^b in Group(a))
then
rootorder:=Order(a);
m:=First([1..rootorder],i->
(a^i=a^b and 1=i^divisor mod rootorder));
fgrp2pairmap:=InverseGeneralMapping(MappingByFunction(
Domain(Cartesian([1..Order(a)],[1..Order(b)])),fgrp,
pair->a^(pair[1]-1)*b^(pair[2]-1))
);
int2Gmap:=MappingByFunction(Domain([1..Size(Gdata.Glist)]),group,
i->Gdata.Glist[i]);
Add(returnlist,
rec(Nsg:=Nsg,alpha:=ANFAutomorphism(CF(rootorder),m),
root:=E(rootorder),fgrp:=fgrp,epi:=epi,a:=a,b:=b,
int2pairtable:=List([1..Size(group)],
i->i^(int2Gmap*epi*fgrp2pairmap)))
);
fi;
od;
return returnlist;
end);
#############################################################################
##
#O NormalSubgroupsForRep( <groupdata>,<divisor> ) calculates normal subgroups to use with `OrderedSigs'
##
#InstallMethod(NormalSubgroupsForRep,
# [IsMagmaWithInverses,IsInt],
# function(group,divisor)
# local returnlist, normals, Nsg, epi, fgrp, gens, b, a,
# rootorder, m, root;
#
# returnlist:=[];
# normals:=Set(Filtered(NormalSubgroups(group),i->
# (Index(group,i) mod divisor=0)
# and not Size(i)=Size(group) and not Size(i)=1
# and not Index(group,i)=divisor)
# );
# normals:=Filtered(normals,i->not IsAbelian(FactorGroup(group,i)));
# for Nsg in normals
# do
# epi:=NaturalHomomorphismByNormalSubgroup(group,Nsg);
# fgrp:=ImagesSource(epi);
# fgrp:=FactorGroup(group,Nsg);
# gens:=MinimalGeneratingSet(fgrp);
# b:=First(gens,i->Order(i)=divisor);
# a:=First(gens,i->Order(i)<>divisor);
# if Size(gens)=2 and b<>fail and (a^b in Group(a))
# then
#
# rootorder:=Order(a);
# m:=First([1..rootorder],i->
# (a^i=a^b and 1=i^divisor mod rootorder));
# Add(returnlist,
# rec(Nsg:=Nsg,alpha:=ANFAutomorphism(CF(rootorder),m),
# root:=E(rootorder),fgrp:=fgrp,epi:=epi,a:=a,b:=b));
# fi;
# od;
# return returnlist;
#end);
#############################################################################
##
#O OrderedSigs
##
InstallMethod(OrderedSigs,"for difference sets in certain groups",
[IsSmallList,IsPosInt,IsGeneralMapping,IsCyc],
function(coeffSums,absSum,alpha,root)
local List2Number, TestTuple, rorder, perm, permorder, src,
blockshifts, blockshiftperms, PermTupleEmbedding,
rightsideMatrix, m, rshift, cc, ccac, ccacdp,
rootmults, block, tuple, b, acGroup, stabGroup,
sortedcoeffSums, unsortingPerm, coeffSet, partSet,
absClassDict, abscoordinates, searchtuples, aimSet,
absClassTuples, returnlist, lastEntry, absClassTuple,
cartesian, lastone, rawtuple, tuples, tup, splittup,
cyc;
if not (IsListOfIntegers(coeffSums) and IsRootOfUnity(root))
then
Error("Argumtents are of wrong type!");
fi;
List2Number:=function(list);
return Sum(CoeffList2CyclotomicList(list,root));
end;
TestTuple:=function(cycrow,pi,gamma,matrix)
if not (Size(cycrow)=Order(pi) and Order(pi)=Order(gamma)
and Order(gamma)=Size(matrix))
then # this should never happen!
Error("I will not buy this record, it is scratched!");
fi;
return ForAll([0..Size(cycrow)-1],i->cycrow*Permuted(List(cycrow,j->
ComplexConjugate(j)^(gamma^i)),pi^i)
=matrix[1][i+1]);
end;
rorder:=Order(root);
perm:=PermList(Concatenation([2..Size(coeffSums)],[1]));
permorder:=Order(perm);
if not Order(alpha^Size(coeffSums))=1
then
Error("Wrong form of matrix!");
fi;
src:=[1..rorder];
blockshifts:=List([1..Size(coeffSums)],i->(i-1)*rorder+src);
blockshiftperms:=List(blockshifts,dst->MappingPermListList(src,dst));
PermTupleEmbedding:=function(permtup)
return Product(List([1..Size(permtup)],i->permtup[i]^blockshiftperms[i]));
end;
rightsideMatrix:=absSum*IdentityMat(Size(coeffSums));
m:=First([1..rorder-1],i->root^alpha=root^i);
rshift:=PermList(Concatenation([2..rorder],[1]));
cc:=ANFAutomorphism(CF(rorder),-1);
ccac:=MinimalGeneratingSet(Action(Group(cc),List([1..rorder],i->root^(i-1))))[1];
ccacdp:=PermTupleEmbedding(List([1..Size(coeffSums)],i->ccac));
rootmults:=[];
for block in [1..Size(coeffSums)]
do
tuple:=[];
tuple[block]:=0;
for b in [1..Size(coeffSums)-1]
do
tuple[block^(perm^b)]:=(tuple[block^(perm^(b-1))]+1)*m mod rorder;
od;
Info(DebugRDS,1,tuple);
Add(rootmults,List([1..Size(tuple)],i->rshift^tuple[i]));
od;
Apply(rootmults,i->PermTupleEmbedding(i));
acGroup:=Group(Concatenation(rootmults,[ccacdp]));
stabGroup:=Stabilizer(Group(rootmults),[2*rorder+1..Size(coeffSums)*rorder],OnTuples);
sortedcoeffSums:=ShallowCopy(coeffSums);
unsortingPerm:=Inverse(Sortex(sortedcoeffSums));
coeffSet:=Set(sortedcoeffSums);
partSet:=List(coeffSet,i->[i,CycsGivenCoeffSum(i,root)]);
absClassDict:=List(sortedcoeffSums,i->First(partSet,j->i=j[1])[2]);
abscoordinates:=List(absClassDict,i->Set(i,j->j[1]));
searchtuples:=Cartesian(abscoordinates{[1..Size(abscoordinates)-1]});
Info(DebugRDS,2,"|searchtuples|=",Size(searchtuples));
aimSet:=Set(abscoordinates[Size(abscoordinates)]);
absClassTuples:=[];
returnlist:=[];
for tuple in searchtuples
do
lastEntry:=absSum-Sum(tuple);
if lastEntry in aimSet
then
absClassTuple:=List([1..Size(tuple)],i->
List(Filtered(absClassDict[i],j->j[1]=tuple[i]),k->k[2]));
Apply(absClassTuple,Concatenation);
cartesian:=Cartesian(absClassTuple);
Apply(cartesian,Concatenation);
cartesian:=List(Orbits(stabGroup,cartesian,Permuted),Representative);
lastone:=List(Filtered(absClassDict[Size(tuple)+1],j->j[1]=lastEntry),k->k[2]);
lastone:=Concatenation(lastone);
Add(absClassTuples,[cartesian,lastone]);
fi;
od;
Info(DebugRDS,2,"|absClassTuples|=",Size(absClassTuples));
returnlist:=[];
for rawtuple in absClassTuples
do
tuples:=List(rawtuple[1],i->List(rawtuple[2],j->Concatenation([i,j])));
tuples:=Concatenation(tuples);
tuples:=List(Orbits(acGroup,tuples,Permuted),Representative);
Info(DebugRDS,3,Size(tuples));
for tup in tuples
do
splittup:=List2Tuples(tup,Size(coeffSums));
cyc:=List(splittup,List2Number);
if TestTuple(cyc,perm,alpha,rightsideMatrix)
then
Add(returnlist,tup);
fi;
od;
od;
returnlist:=Concatenation(List(returnlist,i->Orbit(acGroup,i,Permuted)));
returnlist:=Set(returnlist,i->List2Tuples(i,Size(coeffSums)));
Apply(returnlist,i->Permuted(i,unsortingPerm));
return Set(returnlist);
end);
#############################################################################
##
#O OrderedSignatureOfSet(<set>,<normal_data>)
##
InstallMethod(OrderedSignatureOfSet,
"for ordinary difference sets of special form",
[IsDenseList,IsRecord],
function(set,normal_data)
local table, returnlist, image, i;
table:=normal_data.int2pairtable;
returnlist:=NullMat(Order(normal_data.b),Order(normal_data.a));
image:=Collected(List(set,i->table[i]));
for i in image
do
returnlist[i[1][2]][i[1][1]]:=i[2];
od;
return returnlist;
end);
#############################################################################
##
#E END
##