This chapter contains an important tool for the generation of difference sets. It is called the ``coset signature'' and is an invariant for equivalence of partial relative difference sets. For large λ, there is an invariant calculated by MultiplicityInvariantLargeLambda. This invariant can be used complementary to the coset signature and is explained in section RDS:An invariant for large lambda.
Most of the methods explained here are not commonly used. If you do not want to know how coset signatures work in detail, you can safely skip a large part of this and go straight to the explanation of SignatureDataForNormalSubgroups and ReducedStartsets.
The functions RDSFactorGroupData, MatchingFGData will be interesting for you, if you look for difference sets with the same parameters in different gorups. SignatureDataForNormalSubgroups and SigInvariant
The last section (RDS:Blackbox functions) of this chapter has some functions which allow the user to use coset signatures with even less effort. But be aware that these functions make choices for you that you probably do not want if you do very involved calculations. In particular, the coset signatures are not stored globally and hence cannot be reused. For a demonstration of these easy-to-use functions, see chapter RDS:A basic example
Let R ⊆ G be a (partial) relative difference set (for definition see Introduction) with forbidden set N ⊆ G. Let U ≤ G be a normal subgroup and C={g1,..., g|G:U|} be a system of representatives of G/U.
The intersection number of R with Ugi is defined as vi=|R∩Ugi|. For every normal subgroup U ≤ G the multiset {|R∩Ugi| :gi ∈ C} is called ``coset signature of R (relative to U)''.
Let D ⊆ G be a relative difference set and {v1,...,v|G:U|} its coset signature. Then the following equations hold (see Bruck55},\cite{RoederDiss):
|
Given a group G, the forbidden set N ⊆ G and some normal subgroup U ≤ G, the right sides of this equations are known. So we may ask for tuples (v1,...,v|G:U|) solving this system of equations. Of course, we index the vi with the elements of G/U, so the last equation poses conditions to the ordering of the tuple (v1,...,v|G:U|).
So we call any multiset {v1,...,v|G:U|} solving the above equations an ``admissible signature'' for U.
CosetSignatureOfSet( set, cosets ) F
CosetSignatureOfSet( set,cosets) returns the ordered list of
intersection numbers of set. That is, the size of the intersection
of set with each Element of cosets.
Note that it is not tested, if cosets is really a list of cosets.
CosetSignatureOfSet( set,cosets) works for any List set and any
list of lists cosets. So be careful!
gap> G:=SymmetricGroup(5);; gap> A:=AlternatingGroup(5);; gap> CosetSignatureOfSet([(1,2),(1,5),(1,2,3)],RightCosets(G,A)); [ 1, 2 ] gap> CosetSignatureOfSet([(1,2),(1,5),(1,2,3)],[A]); [ 1 ] gap> CosetSignatureOfSet([(1,2),(1,5),(1,2,3)],[[(1,2),(1,2,3)],[(3,2,1)]]); [ 0, 2 ]
CosetSignatures( Gsize, Usize, diffsetorder ) O
CosetSignatures( Gsize, Nsize, Usize, Intersectsizes, k, lambda ) O
CosetSignatures( Gsize,Usize,diffsetorder) returns all
Gsize /Usize tuples such that the sum of the squares of each tuple
equals Usize+diffsetorder. And the sum of each tuple equals
diffsetorder+1.
These are necessary conditions for signatures of difference sets and normal subgroups of order Usize in groups of order Gsize (see The Coset Signature).
CosetSignatures( Gsize,Nsize,Usize,Intersectsizes,k,lambda)
Calculates all multiset meeting some conditions for signatures of relative
difference sets and normal subgroups of order Usize in groups of
order Gsize (see The Coset Signature).
Here Nsize is the size of the forbidden group,
Intersectsizes is a list of integers determining the size of the
intersection of the forbidden set and the normal Subgroup of order Usize.
The pararmeters k and lambda are the usual ones for designs.
CosetSignatures returns a list containing one pair for each entry i of
Intersectsizes. The first entry of this pair is
[Gsize ,Nsize ,Usize ,i ,k ,lambda ] and the second one is a list
of admissible signatures with these parameters.
gap> CosetSignatures(256,16,64,[1,4,8,16],17,1);
[ [ [ 256, 16, 64, 1, 17, 1 ], [ ] ],
[ [ 256, 16, 64, 4, 17, 1 ], [ [ 3, 4, 4, 6 ] ] ],
[ [ 256, 16, 64, 8, 17, 1 ], [ [ 4, 4, 4, 5 ] ] ],
[ [ 256, 16, 64, 16, 17, 1 ], [ ] ] ]
#And for an ordinary difference set of order 16.
gap> CosetSignatures(273,1,39,[1],17,1);
[ [ [ 273, 1, 39, 1, 17, 1 ],
[ [ 0, 1, 2, 3, 3, 4, 4 ], [ 0, 2, 2, 2, 3, 3, 5 ],
[ 1, 1, 1, 2, 4, 4, 4 ], [ 1, 1, 1, 3, 3, 3, 5 ],
[ 1, 1, 2, 2, 2, 4, 5 ] ] ] ]
TestSignatureLargeIndex( sig, group, Normalsg[, factorgrp] ) O
this does only work for ordinary difference sets, not for relative difference sets in general
TestSignatureLargeIndex(sig,group,Normalsg[,factorgrp]) tests
if sig meets some necessary conditions of The Coset Signature to be
a signature for a difference set in group for the normal subgroup
Normalsg. factorgrp is the factorgroup group/Normalsg.
The returned value is true or false resp.
TestSignatureCyclicFactorGroup( sig, Nsize ) O
This does only work for ordinary difference sets, not for relative difference sets in general
TestSignatureCyclicFactorGroup(sig,Nsize) test if sig meets
meets some necessary conditions of The Coset Signature to be a signature
for a difference set in some group, which has a normal subgroup of
size Nsize such that the factor group is cyclic.
The returned value is true or false resp.
TestedSignatures( sigs, group, Normalsg[, maxtest][, moretest] ) O
this does only work for ordinary difference sets, not for relative difference sets in general
Let sigs be a list of possible signatures as returned by CosetSignatures. Let Normalsg be a subgroup of group. For each signature in sigs, the necessary conditions described in The Coset Signature are tested to decide if the signature can be a signature of a difference set in group for for the normal subgroup Normalsg.
As this involves computation for all permutations of the signature, this
can be very costly. The argument maxtest determines how many
permutations are admissible. If maxtest=0, all signatures are tested,
regardless of how much work is necessary for this. If a signature has
too many permutations, it is returned without test. Even though it is
not wise, maxtest=0 is the default option.
If InfoLevel(InfoRDS)indexInfoRDS@ttInfoRDS is at least 2,
information about skipped signatures is echoed.
If the boolean value moretest is false and all signatures in sigs but the last one are found to be not admissible, the last one is returned without test. This saves the time to test the last signature, but if chances are that there is no difference set in group, this may also give away a chance to find out early (every difference set has signatures, so no admissible signature means that no difference set can exist). Default is true.
TestedSignatures calls TestSignatureCyclicFactorGroup or
TestSignatureLargeIndex and returns a sublist of sigs.
gap> G:=SmallGroup(273,2);;
gap> N:=First(NormalSubgroups(G),g->Order(g)=39);
Group([ f1, f3 ])
gap> sigs:=CosetSignatures(273,1,39,[1],17,1);
[ [ [ 273, 1, 39, 1, 17, 1 ],
[ [ 0, 1, 2, 3, 3, 4, 4 ], [ 0, 2, 2, 2, 3, 3, 5 ],
[ 1, 1, 1, 2, 4, 4, 4 ], [ 1, 1, 1, 3, 3, 3, 5 ],
[ 1, 1, 2, 2, 2, 4, 5 ] ] ] ]
gap> TestedSignatures(sigs[1][2],G,N);
[ [ 1, 1, 1, 2, 4, 4, 4 ], [ 1, 1, 1, 3, 3, 3, 5 ] ]
TestedSignaturesRelative( sigs, fgdata, [, maxtest][, moretest] ) O
TestedSignaturesRelative takes a list sigs of lists of integers and
returns a those which may be signatures of relative difference sets with
forbidden set.
fgdata is a record as returned by
RDSFactorGroupData(U,N,lambda,Gdata)
If maxtest is set, a signature s is only tested if
NrPermutationsList(s)
is less than maxtest if maxtest is set to 0, all signatures are tested
this is the default.
If moretest is tue, a signature is tested even if it is the only one left.
This means we do not assume that there must be an admissable signature at all.
The default for moretest is true.
SigInvariant( diffset , data ) O
Given a partial relative difference set diffset and a list of records with entries cosets and sigs. Here cosets is a full list of cosets and sigs is a list of signatures that may occur for relative difference sets.
For each record rec in data, the intersection numbers of
diffset with the cosets of rec.cosets are computed stored in
a set sig. If none of the signatures in rec.sigs is pointwise
greater or equal sig, SigInvariant( diffset,data) returns `fail.
Otherwise sig is added to a list of signatures that is returned.
Note the returned invariant is that of diffset∪{1}.
The output from SignatureDataForNormalSubgroups can be used as data.
gap> G:=SmallGroup(273,2);
<pc group of size 273 with 3 generators>
gap> Gdata:=PermutationRepForDiffsetCalculations(G);;
gap> N:=First(NormalSubgroups(G),g->Order(g)=39);
Group([ f1, f3 ])
gap> sigs:=CosetSignatures(273,1,39,[1],17,1);
[ [ [ 273, 1, 39, 1, 17, 1 ],
[ [ 0, 1, 2, 3, 3, 4, 4 ], [ 0, 2, 2, 2, 3, 3, 5 ],
[ 1, 1, 1, 2, 4, 4, 4 ], [ 1, 1, 1, 3, 3, 3, 5 ],
[ 1, 1, 2, 2, 2, 4, 5 ] ] ] ]
gap> TestedSignatures(sigs[1][2],G,N);
[ [ 1, 1, 1, 2, 4, 4, 4 ], [ 1, 1, 1, 3, 3, 3, 5 ] ]
gap> sigs:=TestedSignatures(sigs[1][2],G,N);
[ [ 1, 1, 1, 2, 4, 4, 4 ], [ 1, 1, 1, 3, 3, 3, 5 ] ]
gap> ## calculate cosets in permutation notation:
gap> rc:=List(RightCosets(G,N),i->GroupList2PermList(Set(i),Gdata));;
gap> data:=[rec(cosets:=rc,sigs:=sigs)];;
gap> SigInvariant([3,4,5],data);
[ [ [ 0, 0, 0, 0, 0, 1, 3 ], 1 ] ]
For an example using SignatureDataForNormalSubgroups see the example after RDS:ReducedStartsets below.
SignatureDataForNormalSubgroups( Normals, globalSigData, forbiddenSet, Gdata, parameters ) O
Let Gdata be a record as returned by PermutationRepForDiffsetCalculations. Let Normals be a list of normal subgroups of Gdata.G, and forbiddenSet the forbidden set (as set of group elements or group).
parameters must be a list of length 4 of the form [k,lambda,maxtest,moretest]
with k the length of the relative difference set to be constructed and lambda the parameter
as always. maxtest and moretest are passed to TestedSignaturesRelative and must be set.
SignatureDataForNormalSubgroups returns a list containing one record for each group U in
Normals. This record contains:
Moreover, the list globalSigData is used to store global information which can be reused with other groups. The ith entry of globalSigData is a list of records that contains all known information about subgroups of order i. Each of these records has the following components:
The list globalSigData can be used if different groups are studied. If a group has a normal subgroup with parameters (in the sense of .cspara) listed in globalSigData, the signatures from a previous calculation may be used. Of course, the factor groups have to be checked first. This check is done with MatchingFGData or MatchingFGDataNonGrp.
So the second run of SignatureDataForNormalSubgroups with the same parameters and different
Gdata and Normals will normally be much faster, as the signatures are already stored in
globalSigData. Note that maxtest and moretest are not stored. So a second run with
larger maxtest will not result in a recalculation of signatures.
gap> G:=CyclicGroup(57);
<pc group of size 57 with 2 generators>
gap> Gdata:=PermutationRepForDiffsetCalculations(G);;
gap> SignatureDataForNormalSubgroups(NormalSubgroups(Gdata.G),sigdata,
> [One(Gdata.G)],Gdata,[8,1,10^6,true]); # for ordinary diffset of order 7.
[ rec( subgroup := Group([ f1*f2^6 ]),
sigs := [ [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2 ] ],
cosets := [ [ 1, 20, 40 ], [ 3, 23, 43 ], [ 6, 26, 46 ], [ 9, 29, 49 ],
[ 12, 32, 52 ], [ 15, 35, 55 ], [ 18, 38, 57 ],
[ 4, 21, 41 ], [ 7, 24, 44 ], [ 10, 27, 47 ],
[ 13, 30, 50 ], [ 16, 33, 53 ], [ 19, 36, 56 ],
[ 2, 22, 39 ], [ 5, 25, 42 ], [ 8, 28, 45 ], [ 11, 31, 48 ],
[ 14, 34, 51 ], [ 17, 37, 54 ] ] ),
rec( subgroup := Group([ f2 ]), sigs := [ [ 1, 3, 4 ] ],
cosets := [ [ 1, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42,
45, 48, 51, 54 ],
[ 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50,
53, 56 ],
[ 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46, 49,
52, 55, 57 ] ] ) ]
gap> Filtered([1..Size(sigdata)],i->IsBound(sigdata[i]));
[ 3, 19 ]
gap> Size(sigdata[3]);
2
gap> sigdata[3][1].cspara;sigdata[3][2].cspara;
[ 57, 1, 3, 1, 7, 1 ]
[ 57, 1, 3, 1, 8, 1 ]
The following three functions are used by SignatureDataForNormalSubgroups. If you do not want to write your own function for signature management, you might not need them.
RDSFactorGroupData( U, N, lambda, Gdata ) O
takes the subgroup U of G, the forbidden set N as a subgroup or
subset of G and the record of data Gdata as returned by
PermutationRepForDiffsetCalculations(G) and returns a record containing
MatchingFGDataNonGrp( fgdatalist, fgmatchdata ) O
Let fgdatalist be a list of records and fgmatchdata a record with components
.fg, .Nfg and .fgintersect as returned by RDSFactorGroupData.
Then MatchingFGDataNonGrp returns the entry of fgdatalist that defines
the same admissible signatures as fgmatchdata. If no such entry exists,
fail is returned.
The forbidden set N is not assumed to be a group.
MatchingFGData( fgdatalist, fgmatchdata ) O
Let fgdatalist be a list of records and fgmatchdata a record with components
.fg, .Nfg, .fgintersect and .fgaut as returned by RDSFactorGroupData.
Then MatchingFGDataNonGrp returns the entry of fgdatalist that defines
the same admissible signatures as fgmatchdata. If no such entry exists,
fail is returned.
Here the forbidden set N has to be a group.
ReducedStartsets( startsets, autlist, csdata, Gdata ) O
ReducedStartsets( startsets, autlist, func, Gdata ) O
Let startsets be a set of partial relative difference sets, autlist a
list of permutation groups and Gdata record returned by
PermutationRepForDiffsetCalculations.
Then ReducedStartsets partitions the list startsets according to the
values of the function func and performs a test for equivalence on the
elements of the partition. The list returned is a sublist
of startsets of pairwise non-equivalent partial relative difference sets
if func is an invariant for partial relative difference sets. All elements
for which func returns fail are discarded.
If a list csdata of records as used for SigInvariant (i.e. containing
.cosets and .signatures) is pased, then ReducedStartsets
uses SigInvariant for func.
gap> G:=CyclicGroup(57); <pc group of size 57 with 2 generators> gap> Gdata:=PermutationRepForDiffsetCalculations(G);; gap> cosetsigs:=SignatureDataForNormalSubgroups(NormalSubgroups(Gdata.G), > sigdata, [One(Gdata.G)],Gdata,[8,1,10^6,true]);; gap> SigInvariant([3,4,5,9],cosetsigs); [ [ [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1 ], 1 ], [ [ 1, 1, 3 ], 1 ] ] gap> ssets:=AllDiffsets([],2,[],Gdata);; gap> Size(ssets); 1458 gap> Size(ReducedStartsets(ssets,[Group(())],cosetsigs,Gdata)); #I Size 1458 #I 5/ 0 @ 0:00:00.126 486 gap> Size(ReducedStartsets(ssets,[Gdata.Ai],cosetsigs,Gdata)); #I Size 1458 #I 5/ 0 @ 0:00:00.123 17
MaxAutsizeForOrbitCalculation V
In ReducedStartsets, a bound is needed to decide if Orbit or
RepresentativeAction should be used. If the group is larger than
MaxAutsizeForOrbitCalculation@RDS, RepresentativeAction is used.
The default value for maxAutsizeForOrbitCalculation is 5*106.
If you want to change it, you will have to edit the file sigs.gd.
MultiplicityInvariantLargeLambda( set, Gdata ) O
Let set be a partial relative difference set with λ > 1.
Set P:=AllPresentables(set,Gdata) then the set of multiplicities
of P is an invariant for partial relative difference sets.
MultiplicityInvariantLargeLambda returns a list in a form as Collected
does.
gap> G:=CyclicGroup(7);;Gdata:=PermutationRepForDiffsetCalculations(G);; gap> AllPresentables([2,3],Gdata); [ 2, 3, 7, 2, 7, 6 ] gap> MultiplicityInvariantLargeLambda([2,3],Gdata); [ [ 1, 2 ], [ 2, 2 ] ](Read this output as: two elements occur once and two occur twice).
This invariant can be used for ReducedStartsets complementary to the signature invariant by defining
gap> partfunc:=function(list) > local sig; > if sig=fail > then return fail; > fi; > return [MultiplicityInvariantLargeLambda(list,Gdata),SigInvariant(list,sigdata)]; > end; function( list ) ... end
partfunc can then be passed to ReducedStartsets. Of course, sigdata has to be the list of records defining the coset signatures.
Here are a few functions used in chapter RDS:A basic example. These are meant as black boxes for quick tests. Some of them make choices for you which might not be suitable to the chase you consider, so for serious studies, consider using the more complicated-looking functions above (an example for this comprises chapter RDS:An Example Program).
SignatureData( Gdata, forbiddenSet, k, lambda, maxtest ) F
Let Gdata be a record as returned by PermutationRepForDiffsetCalculations. Let forbiddenSet the forbidden set (as set or group).
k is the length of the relative difference set to be constructed and
lambda the usual parameter. maxtest is the
Then SignatureData calls SignatureDataForNormalSubgroups for
normal subgroups of order at least RootInt(Gdata.G). Here maxtest
is an integer which determines how many permutations of a possible
signature are checked to be a sorted signature. Choose a value of at
least 105. Larger numbers here normaly result in better results
when generating difference sets (making reduction more effective).
SigntureData chooses normal subgroups of Gdata.G and uses
SignatureDataForNormalSubgroups to calculate signature data. The global
data generated by SignatureDataForNormalSubgroups is just discarded.
gap> G:=CyclicGroup(57);;Gdata:=PermutationRepForDiffsetCalculations(G);;
gap> sigdat:=SignatureData(Gdata,[One(Gdata.G)],8,1,10^5);
[ rec( subgroup := Group([ f2 ]), sigs := [ [ 1, 3, 4 ] ],
cosets := [ [ 1, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48, 51, 54 ],
[ 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56 ],
[ 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46, 49, 52, 55, 57 ] ] ) ]
NormalSgsHavingAtMostNSigs( sigdata, n, lengthlist ) F
Let sigdata be a list as returned by SignatureDataForNormalSubgroups, an
integer n and a list of integers lengthlist.
NormalSgsHavingAtMostNSigs filters sigdata and returns
a list of records with components .subgroup and .sigs
is returned, such that for every entry
.subgroup is a normal subgroup of index in lengthlist having at most n
signatures.
SuitableAutomorphismsForReduction( Gdata, normalsg ) F
Given a normal subgroup normalsg of Gdata.G, the function returns a list containing the group of automorphisms of Gdata.G which stabilizes all cosets modulo normalsg. This group is returned as a group of permutations on Gdata.Glist (which is actually the right regular representation). The returned list can be used with StartsetsInCoset.
StartsetsInCoset( ssets, coset, forbiddenSet, aim, autlist, sigdat, Gdata, lambda ) F
Assume, we want to generate difference sets ``coset by coset'' modulo some
normal subgroup.
Let ssets be a (possibly empty) set of startsets, coset the coset from
which to take the elements to append to the startsets from ssets.
Furthermore, let aim be the size of the generated partial difference sets
(that is, the size of the elements from ssets plus the number of elements
to be added from coset). Let autlist be a list of groups of
automorphisms (in permutation representation) to use with the reduction
algorithm. Here the output from SuitableAutomorphismsForReduction can be
used.
And Gdata and sigdat are the records as returned by
PermutationRepForDiffsetCalculations and
SignatureDataForNormalSubgroups (or SignatureData, alternatively). The
parameter lambda is the usual one for difference sets (the number of ways
of expressing elements outside the forbidden set as quotients).
Then StartsetsInCoset returns a list of partial difference sets (a list of
lists of integers) of length aim.
The list of permutation groups autlist is used for equivalence testing. Each equivalence test is performed calculating equivalence with respect to the first group, one element per equivalence class is retained and the equivalence test is repeated using the second group from autlist... Using an ascending list of automorphism groups can speed up the process of equivalence testing.
gap> G:=CyclicGroup(57);;Gdata:=PermutationRepForDiffsetCalculations(G);; gap> sigdat:=SignatureData(Gdata,[One(Gdata.G)],8,1,10^5);; gap> N:=First(NormalSubgroups(G),n->Size(n)=19); gap> auts:=SuitableAutomorphismsForReduction(Gdata,N); [ <permutation group of size 18 with 3 generators> ] gap> g:=One(G);;while g in N do > g:=Random(G); > od; gap> coset:=GroupList2PermList(Set(RightCoset(N,g)),Gdata); [ 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56 ] gap> Size(StartsetsInCoset([],coset,[],4,auts,sigdat,Gdata,1)); #I Size 19 #I 1/ 0 @ 0:00:00.003 #I Size 26 #I 1/ 0 @ 0:00:00.001 #I -->10 @ 0:00:00.004 #I Size 88 #I 1/ 0 @ 0:00:00.003 #I -->45 @ 0:00:00.018 #I Size 125 #I 1/ 0 @ 0:00:00.006 #I -->64 @ 0:00:00.031 64 gap> Size(StartsetsInCoset([],coset,[],4,[Group(())],sigdat,Gdata,1)); #I Size 19 #I 1/ 0 @ 0:00:00.000 #I Size 136 #I 1/ 0 @ 0:00:00.004 #I -->136 @ 0:00:00.024 #I Size 648 #I 1/ 0 @ 0:00:00.021 #I -->648 @ 0:00:00.310 #I Size 1140 #I 1/ 0 @ 0:00:00.036 #I -->1140 @ 0:00:00.980 1140
[Up] [Previous] [Next] [Index]
rds manual