\Chapter{General concepts} In this chapter, we first give a definition of relative difference sets and outline a part of the theory. Then we have a quick look at the way difference sets are represented in {\RDS}. After that, some basic methods for the generation of difference sets are explained. If you already read chapter "RDS:A basic example" and want to know what "StartsetsInCoset" really does, you may want to read this chapter. The most important method here is "PermutationRepForDiffsetCalculations" as this is the function all searches start with. The main high-level function for difference set generation in this chapter is "ExtendedStartsets". %%%%%%%%%%%%%%%%%%%% \Section{Introduction} %\Input{rds} Let $G$ be a finite group and $N\subseteq G$. The set $R\subseteq G$ with $|R|=k$ is called a ``relative difference set of order $k-\lambda$ relative to the forbidden set $N$'' if the following properties hold: \beginlist%ordered{(a)} \item{(a)} The multiset $\{ a.b^{-1}\colon a,b\in R\}$ contains every nontrivial ($\neq 1$) element of $G-N$ exactly $\lambda$ times. \item{(b)} $\{ a.b^{-1}\colon a,b\in R\}$ does not contain any non-trivial element of $N$. \endlist Relative difference sets with $N=1$ are called (ordinary) difference sets. As a special case, difference sets with $N=1$ and $\lambda=1$ correspond to projective planes of order $k-1$. Here the blocks are the translates of $R$ and the points are the elements of $G$. In group ring notation a relative difference set satisfies $$ RR^{-1}=k+\lambda(G-N). $$ The set $D\subseteq G$ is called *partial relative difference set* with forbidden set $N$, if $$ DD^{-1}=\kappa+\sum_{g\in G-N}v_gg $$ holds for some $1\leq\kappa\leq k$ and $0\leq v_g \leq \lambda$ for all $g\in G-N$. If $D$ is a relative difference set then ,obviously, $D$ is also a partial relative difference set. Two relative difference sets $D,D'\subseteq G$ are called *strongly equivalent* if they have the same forbidden set $N\subseteq G$ and if there is $g\in G$ and an automorphism $\alpha$ of $G$ such that $D'g^{-1}=D^\alpha$. The same term is applied to partial relative difference sets. Let $D\subseteq G$ be a difference set, then the incidence structure with points $G$ and blocks $\{Dg\;|\;g\in G\}$ is called the *development* of $D$. In short: ${\rm dev} D$. Obviously, $G$ acts on ${\rm dev}D$ by multiplication from the right. If $D$ is a difference set, then $D^{-1}$ is also a difference set. And ${\rm dev} D^{-1}$ is the dual of ${\rm dev} D$. So a group admitting an operation some structure defined by a difference set does also admit an operation on the dual structure. We may therefore change the notion of equivalence and take $\phi$ to be an automorphism or an anti-automorphism. Forbidden sets are closed under inversion, so this gives a ``weak'' sort of strong equivalence. %%%%%%%%%%%%%%%%%%%% \Section{How partial difference sets are represented} Let $G$ be a group. We define an enumeration $\{g_1,\dots,g_n\}=G$ and represent $D\subseteq G$ as a list of integers (where, of course, $i$ represents $g_i$ for all $1\leq i\leq n$). So the automorphism group of $G$ is represented as a permutation group of degree $n$. One of the operations performed most often by methods in {\RDS} is the calculation of quotients in $G$. So we calculate a look-up table for this. This pre-calculation is done by the operation "PermutationRepForDiffsetCalculations". So before you start generating difference set, call this function and work with the data structure returned by it. For an exhaustive search, the ordering of $G$ is very important. To avoid generating duplicate partial difference sets, we would like to represent partial difference sets by *sets*, i.e. ordered lists. But in fact, {\RDS} does *not* assume that partial difference sets are sets. The operations "ExtendedStartSets" and "AllDiffsets" assume that the last element of partial difference set is its maximum. But they don't test it. So if you start from scratch, these methods generate difference sets which are really sets. Whereas the `NoSort' versions disregard the ordering of $G$ and will produce duplicates. The reason for this seemingly strange behaviour is the following: Assume that we have a normal subgroup $U\leq G$ and know that every difference set $D\subseteq G$ contains exactly $n_i$ elements from the $i^{\rm th}$ coset modulo $U$. Then it is natural to generate difference sets by first searching all partial difference sets of length $n_1$ containing entirely of elements of the first coset modulo $U$ and then proceed with the other cosets. This method of difference set generation is normally not compatible with the ordering of $G$. This is why partial difference sets are not required to be *sets*. See chapter "RDS:An Example Program" for an example. %%%%%%%%%%%%%%%%%%%% \Section{Basic functions for startset generation} Defining an enumeration of the a group $G$, every relative difference set may be represented by a list of integers. Indexing $G$ in this way has the advantage of the automorphism group of $G$ being a permutation group acting on the index set for $G$. As relative difference sets are normally calculated in small groups, it is possible to store a complete multiplication table of the group in terms of the enumeration. If not stated otherwise, partial difference sets are always considered to be lists of integers. Note that it is not required for a partial difference set to be a set. \Declaration{PermutationRepForDiffsetCalculations} If `Set(<group>)[1]' is not equal to `One(<group>)', then "PermutationRepForDiffsetCalculations" returns an error message. In this case, calculating a permutation representation helps: \beginexample gap> G:=SL(2,3); SL(2,3) gap> Gdata:=PermutationRepForDiffsetCalculations(G); Error, smallest element of group is not the identity. Try `IsomorphismPermGrou\ p' called from <function>( <arguments> ) called from read-eval-loop Entering break read-eval-print loop ... you can 'quit;' to quit to outer loop, or you can 'return;' to continue brk> quit; gap> G:=Image(IsomorphismPermGroup(G)); Group([ (2,3,5)(6,7,8), (1,2,4,7)(3,6,8,5) ]) gap> Gdata:=PermutationRepForDiffsetCalculations(G); \endexample \Declaration{IsDiffset} \beginexample gap> a:=(1,2,3,4,5,6,7); (1,2,3,4,5,6,7) gap> IsDiffset([a,a^3],Group(a)); true gap> IsDiffset([a,a^3],Group(a),2); false gap> IsDiffset([a,a^2,a^4],Group(a),2); true gap> Gdata:=PermutationRepForDiffsetCalculations(Group(a));; gap> IsDiffset([2,4],Gdata); true \endexample \Declaration{IsPartialDiffset} \beginexample gap> a:=(1,2,3,4,5,6,7); (1,2,3,4,5,6,7) gap> IsPartialDiffset([a],Group(a)); true gap> IsPartialDiffset([a,a^4],Group(a)); false gap> IsPartialDiffset([a,a^4],Group(a),2); true \endexample A partial difference set may be converted from a list of group elements to a list of integers using \Declaration{GroupList2PermList} The inverse operation is performed by \Declaration{PermList2GroupList} \beginexample gap> G:=DihedralGroup(6); <pc group of size 6 with 2 generators> gap> N:=NormalSubgroups(G)[2]; Group([ f2 ]) gap> dat:=PermutationRepForDiffsetCalculations(G); rec( G := <pc group of size 6 with 2 generators>, Glist := [ <identity> of ..., f1, f2, f1*f2, f2^2, f1*f2^2 ], A := <group of size 6 with 2 generators>, Aac := Group([ (3,5)(4,6), (2,4,6) ]), Ahom := <action homomorphism>, Ai := Group([ (3,5), (3,5)(4,6), (2,4,6) ]), diffTable := [ [ 1, 2, 5, 4, 3, 6 ], [ 2, 1, 6, 3, 4, 5 ], [ 3, 6, 1, 2, 5, 4 ], [ 4, 5, 2, 1, 6, 3 ], [ 5, 4, 3, 6, 1, 2 ], [ 6, 3, 4, 5, 2, 1 ] ] ) gap> Nperm:=GroupList2PermList(Set(N),dat); [ 1, 3, 5 ] \endexample In the following functions the record <Gdata> has to contain a matrix <.diffTable> as returned by "PermutationRepForDiffsetCalculations". \Declaration{NewPresentables} \Declaration{AllPresentables} % \beginexample gap> G:=CyclicGroup(7);;dat:=PermutationRepForDiffsetCalculations(G);; gap> AllPresentables([2,3],dat); [ 2, 3, 7, 2, 7, 6 ] gap> NewPresentables([2,3],4,dat); [ 4, 5, 6, 3, 7, 2 ] gap> AllPresentables([1,2,3],dat); Error... \endexample % \Declaration{RemainingCompletions} \beginexample gap> G:=CyclicGroup(7); <pc group of size 7 with 1 generators> gap> dat:=PermutationRepForDiffsetCalculations(G);; gap> RemainingCompletionsNoSort([4],[1..7],dat); [ 2, 3 ] gap> RemainingCompletionsNoSort([4],[1..7],dat,2); [ 2, 3, 6, 7 ] gap> RemainingCompletions([4],[1..7],dat); [ ] gap> RemainingCompletions([4],[1..7],dat,2); [ 6, 7 ] \endexample \Declaration{ExtendedStartsets} \beginexample gap> G:=CyclicGroup(7);;dat:=PermutationRepForDiffsetCalculations(G);; gap> startsets:=[[2],[4],[6]];; gap> ExtendedStartsets(startsets,[1..7],dat); [ [ 2, 4 ], [ 2, 6 ] ] gap> ExtendedStartsets(startsets,[1..7],3,dat); [ [ 2, 4 ] ] gap> ExtendedStartsets(startsets,[1..7],dat,2); [ [ 2, 3 ], [ 2, 4 ], [ 2, 5 ], [ 2, 6 ], [ 4, 6 ], [ 4, 7 ], [ 6, 7 ] ] gap> ExtendedStartsetsNoSort(startsets,[1..7],dat); [ [ 2, 4 ], [ 2, 6 ], [ 4, 2 ], [ 4, 3 ], [ 6, 2 ], [ 6, 5 ] ] \endexample %%%%%%%%%%%%%%%%%%%% \Section{Brute force methods} The following methods can be used to find (partial) difference sets by brute force. More examples are contained in chapter "RDS:AllDiffsets and OneDiffset" \Declaration{AllDiffsets} \Declaration{AllDiffsetsNoSort} If called with <group> rather than <Gdata>, "AllDiffsets" and "AllDiffsetsNoSort" call "PermutationRepForDiffsetCalculations". They then work with sets of integers as difference sets and convert the result back into group notation. As "PermutationRepForDiffsetCalculations" refuses to work if the smallest element of the group is not 1, this does not always work. So a permutation representation for <group> is calculated in this case. However, this is only done for the `NoSort' version and if <partial> is empty. Here is an example: \beginexample gap> m:=[ > [0,1,0,0,0,0,0], > [0,0,1,0,0,0,0], > [0,0,0,1,0,0,0], > [0,0,0,0,1,0,0], > [0,0,0,0,0,1,0], > [0,0,0,0,0,0,1], > [1,0,0,0,0,0,0]];; gap> G:=Group(m); <matrix group with 1 generators> gap> Order(G); 7 gap> Size(AllDiffsets(G)); 6 gap> AllDiffsets([m],G); Error, smallest element of group is not the identity. [...] gap> Size(AllDiffsetsNoSort([m],G)); 2 \endexample The reason for this is the fact that "AllDiffsets" generates difference sets from <partial> by appending only elements which are larger than the last element of <partial>. In a permutation representation, the ordering will be different from the original one, so {\GAP} refuses to calculate the permutation representation and issues an error. "AllDiffsetsNoSort" first appends one element regardless of ordering and then only larger ones. \Declaration{OneDiffset} \Declaration{OneDiffsetNoSort} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %E END startsets.msk %%