\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
%%