startsets.tex

% This file was created automatically from startsets.msk.
% DO NOT EDIT!
\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.

\>PermutationRepForDiffsetCalculations( <group> ) O
\>PermutationRepForDiffsetCalculations( <group>, <autgrp> ) O

For a group <group>, `PermutationRepForDiffsetCalculations(<group>)'
returns a record containing:
\beginlist
 \item{1.} the group <.G>=<group>.
 \item{2.} the sorted list <.Glist>=`Set(<group>)',
 \item{3.} the automorphism group <.A> of <group>,
 \item{4.} the group <.Aac>, which is the permutation action of <A> on the indices of <.Glist>,
 \item{5.} <.Ahom>=`ActionHomomorphism(<.A>,<.Glist>)',
 \item{6.} the group <.Ai> of anti-automorphisms of <.group> acting on the indices of <Glist>,
 \item{7.} the multiplication table <.diffTable> of <.group> in a special form.
\endlist

<.diffTable> is a matrix of integers defined such that 
`<.difftable>[i][j]' is the position of `<Glist>[i](<Glist>[j])^{-1})'
in <Glist> with `<Glist>[1]=One(<group>)'.

`PermutationRepForDiffsetCalculations' runs into an error if 
`Set(<group>)[1]' is not equal to `One(<group>)'.

If <autgrp> is given, `PermutationRepForDiffsetCalculations' will not calculate the
automorphism group of <group> but will take <autgrp> instead without any test.



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

\>IsDiffset( <diffset>, [<forbidden>], <Gdata>, [<lambda>] ) O
\>IsDiffset( <diffset>, [<forbidden>], <group>, [<lambda>] ) O

This function tests if <diffset> is a relative difference set with
forbidden set <forbidden> and parameter <lambda> in the group <group>.
If <Gdata> is the record calculated by "PermutationRepForDiffsetCalculations",
<diffset> and <forbidden> have to be lists of integers. If a group
<group> is given, <diffset> and <forbidden> must consist of elements
of this group.

If <forbidden> is not given, it is assumed to be trivial. If <lambda>
is not given, it is set to $1$. Note that $1$ (`One(<group>)', repectively)
*must not* be element of <diffset>.



\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

\>IsPartialDiffset( <diffset>, [<forbidden>], <Gdata>, [<lambda>] ) O
\>IsPartialDiffset( <diffset>, [<forbidden>], <group>, [<lambda>] ) O

This function tests if <diffset> is a partial relative difference set with
forbidden set <forbidden> and parameter <lambda> in the group <group>.
If <Gdata> is the record calculated by "PermutationRepForDiffsetCalculations",
<diffset> and <forbidden> have to be lists of integers. If a group
<group> is given, <diffset> and <forbidden> must consist of elements
of this group.

If <forbidden> is not given, it is assumed to be trivial. If <lambda>
is not given, it is set to $1$. Note that $1$ (`One(<group>)', repectively)
*must not* be element of <diffset>.


\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 
\>GroupList2PermList( <list>, <Gdata> ) O

converts a list of group elements to integers according to the 
enumeration given in Gdata.Glist.
Here <Gdata> is a record containing .diffTable as returned by 
"PermutationRepForDiffsetCalculations".



The inverse operation is
performed by 
\>PermList2GroupList( <list>, <Gdata> ) O

converts a list of integers into group elements according to the 
enumeration given in Gdata.Glist.
Here <Gdata> is a record containing .diffTable as returned by 
"PermutationRepForDiffsetCalculations".




\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".

\>NewPresentables( <list>, <newel>, <table> ) O
\>NewPresentables( <list>, <newel>, <Gdata> ) O
\>NewPresentables( <list>, <newlist>, <Gdata> ) O
\>NewPresentables( <list>, <newlist>, <table> ) O

`NewPresentables( <list>,<newel>,<Gdata> )' takes a record <Gdata> as 
returned by `PermutationRepForDiffsetCalculations(<group>)'.
For `NewPresentables( <list>,<newel>,<table> )', <table> has to be the
multiplication table in the form of  
`NewPresentables( <list>,<newel>,<Gdata.diffTable>)'

The method returns the unordered list of quotients $d_1<newel>^{-1}$ with 
$d_1\in <list>\cup\{1\}$ (in permutation representation).

When used with a list <newlist>, a list of quotients $d_1d_2^{-1}$ with 
$d_1\in <list>\cup\{1\}$ and $d_2\in <newlist>$ is returned.


\>AllPresentables( <list>, <table> ) O
\>AllPresentables( <list>, <Gdata> ) O

Let <list> be a list of integers representing elements of a group defined 
by <Gdata> (or <table>).
`AllPresentables( <list>,<table>)' returns an unordered list of 
quotients $ab^{-1}$ for all group elements $a,b$  represented by integers 
in <list>. If $1\in <list>$, an error is issued.
The multiplication table <table> has to be of the form as returned by 
"PermutationRepForDiffsetCalculations". And <Gdata> is a record as 
calculated by "PermutationRepForDiffsetCalculations".


%
\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
%	
\>RemainingCompletions( <diffset>, <completions>[, <forbidden>], <Gdata>[, <lambda>] ) O
\>RemainingCompletionsNoSort( <diffset>, <completions>[, <forbidden>], <table>[, <lambda>] ) O

For a partial difference set <diffset>, 
`RemainingCompletions(<diffset>,<completions>,<Gdata>)' returns a 
subset of the *set* <completions>, such that each of its elements may be 
added to <diffset> without it loosing the property to be a partial 
difference set. 
Only elements greater than the last element of <diffset> are returned.

For partial *relative* difference sets, <forbidden> is the forbidden set.

`RemainingCompletionsNoSort' does also return elements from <completions> which
are smaller than `<diffset>[Size(<diffset>)]'. 


\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

\>ExtendedStartsets( <startsets>, <completions>, [<forbiddenset>][, <aim>], <Gdata>[, <lambda>] ) O
\>ExtendedStartsetsNoSort( <startsets>, <completions>, [<forbiddenset>][, <aim>], <Gdata>[, <lambda>] ) O

For a set of partial (relative) difference sets <startsets>, the set of 
all extensions by one element from <completions> is returned.
Here an ``extension'' of a partial diffence set $S$ is a list which has 
one element more than $S$ and contains $S$.

Here <completions> is a set of elements wich may be appended to the lists in 
<startsets> to generate new partial difference sets. For relative difference
sets, the forbidden set <forbiddenset> must be given. 
And the integer <aim> gives the desired total length, i.e. the number 
of elements of <completions> that have to be added to each startset 
plus its length. Note that the elements of <startset> are always extended
by *one* element (if they can be extended). <aim> does only tell how 
many elements from <completions> you want to add. A partial difference
set is only be extended, if there are enough admissible elements in 
<completions>, so if for some $S\in<startsets>$, we have less than 
$<aim>-`Size'(S)$ elements in <completions> which can be added to $S$,
no extension of $S$ is returned. 

If <lambda> is not passed as a parameter, it is assumed to be $1$.

Note that `ExtendedStartsets' does use "RemainingCompletions" while 
`ExtendedStartsetsNoSort' uses "RemainingCompletionsNoSort". 
Note that the partial difference sets generated with `ExtendedStartsetsNoSort'
are *not* sets (i.e. not sorted). This may result in doing work
twice. But it can also be useful, especially when generating difference sets 
``coset by coset''.



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

\>AllDiffsets( [<partial>], <group>, [<lambda>] ) O
\>AllDiffsets( <partial>, [<aim>], <forbidden>, <group>, [<lambda>] ) O
\>AllDiffsets( [<partial>], <Gdata>, [<lambda>] ) O
\>AllDiffsets( <partial>, [<aim>], <forbidden>, <Gdata>, [<lambda>] ) O
\>AllDiffsets( <partial>, <completions>, <aim>, <forbidden>, <Gdata>, <lambda> ) O

Let <partial> be a list of elements of the group <group> which form a
partial relative difference set with parameter <lambda> and forbidden 
set <forbidden> (which is also a set of group elements). That means that 
the every non-trivial element in the list of quotients in elements of
<partial> occurs at most <lambda> times and no element of <forbidden>
is in this set.
Then `AllDiffsets' returns the list of all partial relative difference
sets of length <aim> with parameter <lambda> and forbidden set <forbidden>
which contain <partial>. Only those partial relative difference sets will
be constructed, which start with <partial> and continue with elements
larger than the last element in <partial>.

To calculate *all* difference sets which contain <partial> as a subset,
you can use "AllDiffsetsNoSort".

Note that a difference set is also assumed to 
contain the identity element, but this does not occur in the returned
lists. So a returned difference set contains <aim> elements but actually
represents a set of length <aim>+1, as it still is a partial relative 
difference set when the identity element is added.
If <partial> is not given or the empty set, all difference set in the 
group <group> are calculated. If <lambda> is not given, it is set to 1.
Without <forbidden>, ordinary difference sets are calculated.
If <aim> is not given, it is set to the size of a full relative 
difference set with forbidden set <forbidden> and parameter <lambda>.

Instead of using a group <group>, you can also use the data record 
<Gdata> returned by "PermutationRepForDiffsetCalculations".
In this case, <partial> and <forbidden> must be lists of integers.
In the last form, <completions> must be a list of integers and 
`AllDiffsets' does only extend <partial> by elements from <completions>.


\>AllDiffsetsNoSort( <partial>, <group> ) O
\>AllDiffsetsNoSort( <partial>, <Gdata> ) O
\>AllDiffsetsNoSort( <partial>, [<completions>], <aim>, [<forbidden>], <group>, [<lambda>] ) O
\>AllDiffsetsNoSort( <partial>, [<completions>], <aim>, [<forbidden>], <Gdata>, [<lambda>] ) O

This calculates all partial relative difference sets which contain the partial
relative difference set <partial>. The returned value is a set of lists.
Each of the returned lists starts with the list <partial>.
If <partial> is not a partial relative difference set, the empty list is 
returned. 

Note that despite the name, `AllDiffsetsNoSort' does not calculate all
difference sets as unordered lists. It just calculates all difference 
sets which contain <partial> as a subset.

As it does not only append larger elements to <partial>, `AllDiffsetsNoSort'
works for all groups.



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.

\>OneDiffset( [<partial>], <group>, [<lambda>] ) O
\>OneDiffset( <partial>, [<aim>], <forbidden>, <group>, [<lambda>] ) O
\>OneDiffset( [<partial>], <Gdata>, [<lambda>] ) O
\>OneDiffset( <partial>, [<aim>], <forbidden>, <Gdata>, [<lambda>] ) O
\>OneDiffset( <partial>, <completions>, <aim>, <forbidden>, <Gdata>, <lambda> ) O

This function works exactly like "AllDiffsets", but stops once a 
(partial) relative difference set is found.
This (partial) relative difference set is then returned. If no set 
with the requested property exists, the empty list is returned.

If `OneDiffset' is called using <Gdata> and lists of integers as
<partial> and <forbidden>, then the returned difference set is 
the lexicographically smallest one starting with <partial>.
If the <group>-form is used and <partial> is not empty, `OneDiffset'
does only work, if the smallest element of <group> is the identity.
This is not the case for matrix groups in general.


\>OneDiffsetNoSort( <partial>, <group> ) O
\>OneDiffsetNoSort( <partial>, <Gdata> ) O
\>OneDiffsetNoSort( <partial>, [<completions>], <aim>, [<forbidden>], <group>, [<lambda>] ) O
\>OneDiffsetNoSort( <partial>, [<completions>], <aim>, [<forbidden>], <Gdata>, [<lambda>] ) O

This works exactly as "AllDiffsetsNoSort" does, but stops once a set 
with the desired properties is found and returns it.
If no difference set exists, the empty list is returned.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%E END startsets.msk
%%