- Introduction
- How partial difference sets are represented
- Basic functions for startset generation
- Brute force methods

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.

Let `G` be a finite group and `NsubseteqG`. The set `RsubseteqG`
with `|R|=k` is called a ``relative difference set of order
`k-lambda` relative to the forbidden set `N`'' if the following
properties hold:

- The multiset
`{ a.b`contains every nontrivial (^{-1}colona,binR}`neq1`) element of`G-N`exactly`lambda`times. -
`{ a.b`does not contain any non-trivial element of^{-1}colona,binR}`N`.

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 `DsubseteqG` is called **partial relative difference set**
with forbidden set `N`, if

`
DD ^{-1}=kappa+sum_{ginG-N}v_{g}g
`

holds for some `1leqkappaleqk` and `0leqv _{g} leqlambda` for
all

Two relative difference sets `D,D'subseteqG` are called **strongly
equivalent** if they have the same forbidden set `NsubseteqG` and if
there is `ginG` and an automorphism `alpha` of `G` such that
`D'g ^{-1}=D^alpha`. The same term is applied to partial relative
difference sets.

Let `DsubseteqG` be a difference set, then the incidence structure
with points `G` and blocks `{Dg;|;ginG}` is called the
**development** of `D`. In short: `dev D`. Obviously, `G` acts on
`devD` by multiplication from the right.

If `D` is a difference set, then `D ^{-1}` is also a difference set.
And

Let `G` be a group. We define an enumeration `{g _{1},...,g_{n}}=G` and
represent

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 `UleqG` and know that every
difference set `DsubseteqG` contains exactly `n _{i}` elements from the

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.

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( `

` ) O`

`PermutationRepForDiffsetCalculations( `

`, `

` ) O`

For a group `group`, `PermutationRepForDiffsetCalculations(`

`group``)`

returns a record containing:

- 1.
- the group
`.G`=`group`. - 2.
- the sorted list
`.Glist`=`Set(`

`group``)`

, - 3.
- the automorphism group
`.A`of`group`, - 4.
- the group
`.Aac`, which is the permutation action of`A`on the indices of`.Glist`, - 5.
`.Ahom`=`ActionHomomorphism(`

`.A``,`

`.Glist``)`

,- 6.
- the group
`.Ai`of anti-automorphisms of`.group`acting on the indices of`Glist`, - 7.
- the multiplication table
`.diffTable`of`.group`in a special form.

`.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:

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);

`IsDiffset( `

`, [`

`], `

`, [`

`] ) O`

`IsDiffset( `

`, [`

`], `

`, [`

`] ) 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`.

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

`IsPartialDiffset( `

`, [`

`], `

`, [`

`] ) O`

`IsPartialDiffset( `

`, [`

`], `

`, [`

`] ) 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`.

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

A partial difference set may be converted from a list of group elements to a list of integers using

`GroupList2PermList( `

`, `

` ) 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.

`PermList2GroupList( `

`, `

` ) 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.

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 ]

In the following functions the record `Gdata` has to contain a matrix
`.diffTable` as returned by PermutationRepForDiffsetCalculations.

`NewPresentables( `

`, `

`, `

` ) O`

`NewPresentables( `

`, `

`, `

` ) O`

`NewPresentables( `

`, `

`, `

` ) O`

`NewPresentables( `

`, `

`, `

` ) 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

When used with a list `newlist`, a list of quotients `d _{1}d_{2}^{-1}` with

`AllPresentables( `

`, `

` ) O`

`AllPresentables( `

`, `

` ) 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

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

`RemainingCompletions( `

`, `

`[, `

`], `

`[, `

`] ) O`

`RemainingCompletionsNoSort( `

`, `

`[, `

`], `

`[, `

`] ) 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``)]`

.

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 ]

`ExtendedStartsets( `

`, `

`, [`

`][, `

`], `

`[, `

`] ) O`

`ExtendedStartsetsNoSort( `

`, `

`, [`

`][, `

`], `

`[, `

`] ) 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 `Sin startsets`, we have less than

`Size`

(S)
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''.

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 ] ]

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( [`

`], `

`, [`

`] ) O`

`AllDiffsets( `

`, [`

`], `

`, `

`, [`

`] ) O`

`AllDiffsets( [`

`], `

`, [`

`] ) O`

`AllDiffsets( `

`, [`

`], `

`, `

`, [`

`] ) O`

`AllDiffsets( `

`, `

`, `

`, `

`, `

`, `

` ) 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( `

`, `

` ) O`

`AllDiffsetsNoSort( `

`, `

` ) O`

`AllDiffsetsNoSort( `

`, [`

`], `

`, [`

`], `

`, [`

`] ) O`

`AllDiffsetsNoSort( `

`, [`

`], `

`, [`

`], `

`, [`

`] ) 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:

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

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( [`

`], `

`, [`

`] ) O`

`OneDiffset( `

`, [`

`], `

`, `

`, [`

`] ) O`

`OneDiffset( [`

`], `

`, [`

`] ) O`

`OneDiffset( `

`, [`

`], `

`, `

`, [`

`] ) O`

`OneDiffset( `

`, `

`, `

`, `

`, `

`, `

` ) 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( `

`, `

` ) O`

`OneDiffsetNoSort( `

`, `

` ) O`

`OneDiffsetNoSort( `

`, [`

`], `

`, [`

`], `

`, [`

`] ) O`

`OneDiffsetNoSort( `

`, [`

`], `

`, [`

`], `

`, [`

`] ) 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.

[Up] [Previous] [Next] [Index]

RDS manual

February 2012