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

4 General concepts

Sections

  1. Introduction
  2. How partial difference sets are represented
  3. Basic functions for startset generation
  4. 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.

4.1 Introduction

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:

  1. The multiset { a.b-1colona,binR} contains every nontrivial (neq1) element of G-N exactly lambda times.
  2. { a.b-1colona,binR} does not contain any non-trivial element of 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+sumginG-Nvgg

holds for some 1leqkappaleqk and 0leqvg leqlambda for all ginG-N. If D is a relative difference set then ,obviously, D is also a partial relative difference set.

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 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 phi to be an automorphism or an anti-automorphism. Forbidden sets are closed under inversion, so this gives a ``weak'' sort of strong equivalence.

4.2 How partial difference sets are represented

Let G be a group. We define an enumeration {g1,...,gn}=G and represent DsubseteqG as a list of integers (where, of course, i represents gi for all 1leqileqn). 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 UleqG and know that every difference set DsubseteqG 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.

4.3 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:

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

    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.

    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 d1inlistcup{1} (in permutation representation).

    When used with a list newlist, a list of quotients d1d2-1 with d1inlistcup{1} and d2innewlist 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 1inlist, 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 Sinstartsets, 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 ] ]
    

    4.4 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:

    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
    February 2012