\Chapter{Invariants for Difference Sets} This chapter contains an important tool for the generation of difference sets. It is called the ``coset signature'' and is an invariant for equivalence of partial relative difference sets. For large $\lambda$, there is an invariant calculated by "MultiplicityInvariantLargeLambda". This invariant can be used complementary to the coset signature and is explained in section "RDS:An invariant for large lambda". Most of the methods explained here are not commonly used. If you do not want to know how coset signatures work in detail, you can safely skip a large part of this and go straight to the explanation of "SignatureDataForNormalSubgroups" and "ReducedStartsets". The functions "RDSFactorGroupData", "MatchingFGData" will be interesting for you, if you look for difference sets with the same parameters in different gorups. "SignatureDataForNormalSubgroups" and "SigInvariant" The last section ("RDS:Blackbox functions") of this chapter has some functions which allow the user to use coset signatures with even less effort. But be aware that these functions make choices for you that you probably do not want if you do very involved calculations. In particular, the coset signatures are not stored globally and hence cannot be reused. For a demonstration of these easy-to-use functions, see chapter "RDS:A basic example" %%%%%%%%%%%%%%%%%%%% \Section{The Coset Signature} Let $R \subseteq G$ be a (partial) relative difference set (for definition see "Introduction") with forbidden set $N\subseteq G$. Let $U\leq G$ be a normal subgroup and $C=\{g_1,\dots, g_{|G:U|}\}$ be a system of representatives of $G/U$. The intersection number of $R$ with $Ug_i$ is defined as $v_i=|R\cap Ug_i|$. For every normal subgroup $U\leq G$ the multiset $\{|R\cap Ug_i| \colon g_i\in C\}$ is called ``coset signature of $R$ (relative to $U$)''. Let $D\subseteq G$ be a relative difference set and $\{v_1,\dots,v_{|G:U|}\}$ its coset signature. Then the following equations hold (see \cite{Bruck55},\cite{RoederDiss}): $$ \matrix{ \sum v_i=k\cr \sum v_i^2=\lambda(|U|-|U\cap N|)+k\cr \sum_j v_j v_{ij}= \lambda(|U|-|g_iU \cap N|)&{\rm for }\ g_i\not\in U} $$ where $v_{ij}=|D\cap g_ig_jU|$. If the forbidden set $N$ is a subgroup of $G$ we have $|g_iU\cap N|$ is either $0$ or equal to $|U\cap N|$. Given a group $G$, the forbidden set $N\subseteq G$ and some normal subgroup $U\leq G$, the right sides of this equations are known. So we may ask for tuples $(v_1,\dots,v_{|G:U|})$ solving this system of equations. Of course, we index the $v_i$ with the elements of $G/U$, so the last equation poses conditions to the ordering of the tuple $(v_1,\dots,v_{|G:U|})$. So we call any multiset $\{v_1,\dots,v_{|G:U|}\}$ solving the above equations an ``admissible signature'' for $U$. %In \GAP, admissible signatures are represented by lists as returned by %`Collected' \Declaration{CosetSignatureOfSet} \beginexample gap> G:=SymmetricGroup(5);; gap> A:=AlternatingGroup(5);; gap> CosetSignatureOfSet([(1,2),(1,5),(1,2,3)],RightCosets(G,A)); [ 1, 2 ] gap> CosetSignatureOfSet([(1,2),(1,5),(1,2,3)],[A]); [ 1 ] gap> CosetSignatureOfSet([(1,2),(1,5),(1,2,3)],[[(1,2),(1,2,3)],[(3,2,1)]]); [ 0, 2 ] \endexample \Declaration{CosetSignatures} \beginexample gap> CosetSignatures(256,16,64,[1,4,8,16],17,1); [ [ [ 256, 16, 64, 1, 17, 1 ], [ ] ], [ [ 256, 16, 64, 4, 17, 1 ], [ [ 3, 4, 4, 6 ] ] ], [ [ 256, 16, 64, 8, 17, 1 ], [ [ 4, 4, 4, 5 ] ] ], [ [ 256, 16, 64, 16, 17, 1 ], [ ] ] ] #And for an ordinary difference set of order 16. gap> CosetSignatures(273,1,39,[1],17,1); [ [ [ 273, 1, 39, 1, 17, 1 ], [ [ 0, 1, 2, 3, 3, 4, 4 ], [ 0, 2, 2, 2, 3, 3, 5 ], [ 1, 1, 1, 2, 4, 4, 4 ], [ 1, 1, 1, 3, 3, 3, 5 ], [ 1, 1, 2, 2, 2, 4, 5 ] ] ] ] \endexample \Declaration{TestSignatureLargeIndex} \Declaration{TestSignatureCyclicFactorGroup} \Declaration{TestedSignatures} \beginexample gap> G:=SmallGroup(273,2);; gap> N:=First(NormalSubgroups(G),g->Order(g)=39); Group([ f1, f3 ]) gap> sigs:=CosetSignatures(273,1,39,[1],17,1); [ [ [ 273, 1, 39, 1, 17, 1 ], [ [ 0, 1, 2, 3, 3, 4, 4 ], [ 0, 2, 2, 2, 3, 3, 5 ], [ 1, 1, 1, 2, 4, 4, 4 ], [ 1, 1, 1, 3, 3, 3, 5 ], [ 1, 1, 2, 2, 2, 4, 5 ] ] ] ] gap> TestedSignatures(sigs[1][2],G,N); [ [ 1, 1, 1, 2, 4, 4, 4 ], [ 1, 1, 1, 3, 3, 3, 5 ] ] \endexample \Declaration{TestedSignaturesRelative} \Declaration{SigInvariant} \beginexample gap> G:=SmallGroup(273,2); <pc group of size 273 with 3 generators> gap> Gdata:=PermutationRepForDiffsetCalculations(G);; gap> N:=First(NormalSubgroups(G),g->Order(g)=39); Group([ f1, f3 ]) gap> sigs:=CosetSignatures(273,1,39,[1],17,1); [ [ [ 273, 1, 39, 1, 17, 1 ], [ [ 0, 1, 2, 3, 3, 4, 4 ], [ 0, 2, 2, 2, 3, 3, 5 ], [ 1, 1, 1, 2, 4, 4, 4 ], [ 1, 1, 1, 3, 3, 3, 5 ], [ 1, 1, 2, 2, 2, 4, 5 ] ] ] ] gap> TestedSignatures(sigs[1][2],G,N); [ [ 1, 1, 1, 2, 4, 4, 4 ], [ 1, 1, 1, 3, 3, 3, 5 ] ] gap> sigs:=TestedSignatures(sigs[1][2],G,N); [ [ 1, 1, 1, 2, 4, 4, 4 ], [ 1, 1, 1, 3, 3, 3, 5 ] ] gap> ## calculate cosets in permutation notation: gap> rc:=List(RightCosets(G,N),i->GroupList2PermList(Set(i),Gdata));; gap> data:=[rec(cosets:=rc,sigs:=sigs)];; gap> SigInvariant([3,4,5],data); [ [ [ 0, 0, 0, 0, 0, 1, 3 ], 1 ] ] \endexample For an example using "SignatureDataForNormalSubgroups" see the example after "RDS:ReducedStartsets" below. \Declaration{SignatureDataForNormalSubgroups} \beginexample gap> G:=CyclicGroup(57); <pc group of size 57 with 2 generators> gap> Gdata:=PermutationRepForDiffsetCalculations(G);; gap> SignatureDataForNormalSubgroups(NormalSubgroups(Gdata.G),sigdata, > [One(Gdata.G)],Gdata,[8,1,10^6,true]); # for ordinary diffset of order 7. [ rec( subgroup := Group([ f1*f2^6 ]), sigs := [ [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2 ] ], cosets := [ [ 1, 20, 40 ], [ 3, 23, 43 ], [ 6, 26, 46 ], [ 9, 29, 49 ], [ 12, 32, 52 ], [ 15, 35, 55 ], [ 18, 38, 57 ], [ 4, 21, 41 ], [ 7, 24, 44 ], [ 10, 27, 47 ], [ 13, 30, 50 ], [ 16, 33, 53 ], [ 19, 36, 56 ], [ 2, 22, 39 ], [ 5, 25, 42 ], [ 8, 28, 45 ], [ 11, 31, 48 ], [ 14, 34, 51 ], [ 17, 37, 54 ] ] ), rec( subgroup := Group([ f2 ]), sigs := [ [ 1, 3, 4 ] ], cosets := [ [ 1, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48, 51, 54 ], [ 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56 ], [ 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46, 49, 52, 55, 57 ] ] ) ] gap> Filtered([1..Size(sigdata)],i->IsBound(sigdata[i])); [ 3, 19 ] gap> Size(sigdata[3]); 2 gap> sigdata[3][1].cspara;sigdata[3][2].cspara; [ 57, 1, 3, 1, 7, 1 ] [ 57, 1, 3, 1, 8, 1 ] \endexample The following three functions are used by "SignatureDataForNormalSubgroups". If you do not want to write your own function for signature management, you might not need them. \Declaration{RDSFactorGroupData} \Declaration{MatchingFGDataNonGrp} \Declaration{MatchingFGData} \Declaration{ReducedStartsets} \beginexample gap> G:=CyclicGroup(57); <pc group of size 57 with 2 generators> gap> Gdata:=PermutationRepForDiffsetCalculations(G);; gap> cosetsigs:=SignatureDataForNormalSubgroups(NormalSubgroups(Gdata.G), > sigdata, [One(Gdata.G)],Gdata,[8,1,10^6,true]);; gap> SigInvariant([3,4,5,9],cosetsigs); [ [ [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1 ], 1 ], [ [ 1, 1, 3 ], 1 ] ] gap> ssets:=AllDiffsets([],2,[],Gdata);; gap> Size(ssets); 1458 gap> Size(ReducedStartsets(ssets,[Group(())],cosetsigs,Gdata)); #I Size 1458 #I 5/ 0 @ 0:00:00.126 486 gap> Size(ReducedStartsets(ssets,[Gdata.Ai],cosetsigs,Gdata)); #I Size 1458 #I 5/ 0 @ 0:00:00.123 17 \endexample \Declaration{maxAutsizeForOrbitCalculation} %%%%%%%%%%%%%%%%%%%%%% \Section{An invariant for large lambda} \Declaration{MultiplicityInvariantLargeLambda} \beginexample gap> G:=CyclicGroup(7);;Gdata:=PermutationRepForDiffsetCalculations(G);; gap> AllPresentables([2,3],Gdata); [ 2, 3, 7, 2, 7, 6 ] gap> MultiplicityInvariantLargeLambda([2,3],Gdata); [ [ 1, 2 ], [ 2, 2 ] ] \endexample (Read this output as: two elements occur once and two occur twice). This invariant can be used for "ReducedStartsets" complementary to the signature invariant by defining \begintt gap> partfunc:=function(list) > local sig; > if sig=fail > then return fail; > fi; > return [MultiplicityInvariantLargeLambda(list,Gdata),SigInvariant(list,sigdata)]; > end; function( list ) ... end \endtt <partfunc> can then be passed to "ReducedStartsets". Of course, <sigdata> has to be the list of records defining the coset signatures. %%%%%%%%%%%%%%%%%%%%%% \Section{Blackbox functions} Here are a few functions used in chapter "RDS:A basic example". These are meant as black boxes for quick tests. Some of them make choices for you which might not be suitable to the chase you consider, so for serious studies, consider using the more complicated-looking functions above (an example for this comprises chapter "RDS:An Example Program"). \Declaration{SignatureData} \beginexample gap> G:=CyclicGroup(57);;Gdata:=PermutationRepForDiffsetCalculations(G);; gap> sigdat:=SignatureData(Gdata,[One(Gdata.G)],8,1,10^5); [ rec( subgroup := Group([ f2 ]), sigs := [ [ 1, 3, 4 ] ], cosets := [ [ 1, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48, 51, 54 ], [ 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56 ], [ 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46, 49, 52, 55, 57 ] ] ) ] \endexample \Declaration{NormalSgsHavingAtMostNSigs} \Declaration{SuitableAutomorphismsForReduction} \Declaration{StartsetsInCoset} \beginexample gap> G:=CyclicGroup(57);;Gdata:=PermutationRepForDiffsetCalculations(G);; gap> sigdat:=SignatureData(Gdata,[One(Gdata.G)],8,1,10^5);; gap> N:=First(NormalSubgroups(G),n->Size(n)=19); gap> auts:=SuitableAutomorphismsForReduction(Gdata,N); [ <permutation group of size 18 with 3 generators> ] gap> coset:=GroupList2PermList(Set(RightCoset(N,Random(G))),Gdata); [ 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46, 49, 52, 55, 57 ] gap> Size(StartsetsInCoset([],coset,[],4,auts,sigdat,Gdata,1)); #I Size 19 #I 1/ 0 @ 0:00:00.001 #I Size 20 #I 1/ 0 @ 0:00:00.001 #I -->9 @ 0:00:00.004 #I Size 85 #I 1/ 0 @ 0:00:00.007 #I -->44 @ 0:00:00.033 #I Size 144 #I 1/ 0 @ 0:00:00.006 #I -->64 @ 0:00:00.083 64 gap> Size(StartsetsInCoset([],coset,[],4,[Group(())],sigdat,Gdata,1)); #I Size 19 #I 1/ 0 @ 0:00:00.001 #I Size 136 #I 1/ 0 @ 0:00:00.005 #I -->136 @ 0:00:00.075 #I Size 648 #I 1/ 0 @ 0:00:00.024 #I -->648 @ 0:00:01.597 #I Size 1140 #I 1/ 0 @ 0:00:00.044 #I -->1140 @ 0:00:05.648 1140 \endexample