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 N ⊆ G. The set R ⊆ G with |R|=k is called a ``relative difference set of order k−λ relative to the forbidden set N'' if the following properties hold:
Relative difference sets with N=1 are called (ordinary) difference sets. As a special case, difference sets with N=1 and λ = 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
|
The set D ⊆ G is called partial relative difference set
with forbidden set N, if
|
holds for some 1 ≤ κ ≤ k and 0 ≤ vg ≤ λ for all g ∈ 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′ ⊆ G are called strongly equivalent if they have the same forbidden set N ⊆ G and if there is g ∈ G and an automorphism α of G such that D′g−1=Dα. The same term is applied to partial relative difference sets.
Let D ⊆ G be a difference set, then the incidence structure with points G and blocks {Dg | g ∈ G} 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 dev D−1 is the dual of 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 ϕ to be an automorphism or an anti-automorphism. Forbidden sets are closed under inversion, so this gives a ``weak'' sort of strong equivalence.
Let G be a group. We define an enumeration {g1,...,gn}=G and represent D ⊆ G as a list of integers (where, of course, i represents gi for all 1 ≤ i ≤ 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 ≤ G and know that every difference set D ⊆ G contains exactly ni elements from the ith coset modulo U. Then it is natural to generate difference sets by first searching all partial difference sets of length n1 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.
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:
Set(group),
ActionHomomorphism(.A,.Glist),
.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( 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.
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( 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.
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( 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.
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.
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( 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 d1newel −1 with d1 ∈ list ∪{1} (in permutation representation).
When used with a list newlist, a list of quotients d1d2−1 with d1 ∈ list ∪{1} and d2 ∈ 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 ∈ 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.
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( 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)].
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( 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 ∈ 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''.
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( [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:
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( [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.
[Up] [Previous] [Next] [Index]
rds manual