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

6 An Example Program

Here is a similar example to that in chapter RDS:A basic example. But now we do a little more handwork to see how things work. Now we will calculate the relative difference sets of ``Dembowski-Piper type d'' and order 16. These difference sets represent projective planes which admit a quasiregular collineation group such that the fixed structure is an anti-flag. See DembowskiPiper, Dembowski or RoederDiss for details.

To have a little more output, you may want to increase InfoRDS:

gap> SetInfoLevel(InfoRDS,3);

First, define some parameters and calculate the data needed:

gap> k:=16;;lambda:=1;;groupOrder:=255;; #Diffset parameters
gap> forbiddenGroupOrder:=15;;
gap> maxtest:=10^6;;                     #Bound for sig testing
gap> G:=CyclicGroup(groupOrder);
<pc group of size 255 with 3 generators>
gap> Gdata:=PermutationRepForDiffsetCalculations(G);;
gap> MakeImmutable(Gdata);; 

Now the forbidden group is calculated in a very ineffective way. Then we calculate admissible signatures. As there are only few normal subgroups in G, we calculate them all. For other groups, one should choose more wisely.

gap> N:=First(NormalSubgroups(Gdata.G),i->Size(i)=forbiddenGroupOrder);
Group([ f1*f3^9, f2*f3^10 ])
gap> globalSigData:=[];;
gap> normals:=Filtered(NormalSubgroups(Gdata.G),n->Size(n) in [2..groupOrder-1]);; 
gap> sigdat:=SignatureDataForNormalSubgroups(normals,globalSigData,
>                             N,Gdata,[k,lambda,maxtest,true]);;

The last step gives better results, if a larger maxtest is chosen. But it also takes more time. To find a suitable maxtest, the output of SignatureDataForNormalSubgroups can be used, if InfoLevel(InfoRDS) is at least 2. Note that for recalculating signatures, you will have to reset globalSigData to []. Try experimenting with maxtest to see the effect of signatures for the generation of startsets.

Now examine the signatures found. Look if there is a normal subgroup which has only one admissible signature (of course, you can also use NormalSgsHavingAtMostNSigs here):

gap> Set(Filtered(sigdat,s->Size(s.sigs)=1 and Size(s.sigs[1])<=5),i->i.sigs);
[ [ [ 0, 4, 4, 4, 4 ] ], [ [ 4, 4, 8 ] ] ]

Great! we'll take the subgroup of index 3. The cosets modulo this group will be used to generate startsets and we assume that the trivial coset contains 8 elements of the difference set. So we generate startsets in U and make a first reduction. For this, we need U and N as lists of integers (recall that difference sets are asumed to be lists of integers). We will call these lists Up and Np. Furthermore, we will have to choose a suitable group of automorphisms for reduction. As G is cyclic, we may take Gdata.Aac here. A good choice is the stabilizer of all cosets modulo U. Yet sometimes larger groups may be possible. For example if we want to generate start sets in U and then do a brute force search. In this case, we may take the stabilizer of U for reduction.

gap> U:=First(sigdat,s->s.sigs=[ [ 4, 4, 8 ] ]).subgroup; 
Group([ f2, f3 ])
gap> cosets:=RightCosets(G,U);
gap> U1:=cosets[2];;U2:=cosets[3];;
gap> Up:=GroupList2PermList(Set(U),Gdata);;  
gap> Np:=GroupList2PermList(Set(N),Gdata); 
[ 1, 12, 25, 43, 78, 97, 115, 116, 134, 151, 169, 188, 207, 238, 249 ]
gap> comps:=Difference(Up,Np);; 
gap> ssets:=List(comps,i->[i]);;
gap> ssets:=ReducedStartsets(ssets,[Gdata.Aac],sigdat,Gdata.diffTable); 
#I  Size 80
#I  2/ 0 @ 0:00:00.061
[ [ 3 ], [ 4 ] ]

Observe that 1 is assumed to be element of every difference set and is not recorded explicitly. So the partial difference sets represented by ssets at this point are tt[ [ 1, 3 ], [ 1, 4 ] ]. Now the startsets are extended to size 7 using elements of Up. The runtime varies depending on the output of SignatureDataForNormalSubgroups and hence on maxtest.

gap> repeat 
>     ssets:=ExtendedStartsets(ssets,comps,Np,7,Gdata); 
>     ssets:=ReducedStartsets(ssets,[Gdata.Aac],sigdat,Gdata.diffTable);; 
> until ssets=[] or Size(ssets[1])=7; 
#I  Size 133
#I  3/ 0 @ 0:00:00.133
#I  Size 847
#I  4/ 0 @ 0:00:00.949
#I  Size 6309
#I  4/ 0 @ 0:00:07.692
#I  Size 21527
#I  5/ 0 @ 0:00:28.337
#I  Size 15884
#I  4/ 0 @ 0:00:21.837
#I  Size 1216
#I  4/ 0 @ 0:00:01.758
gap> Size(ssets);
192
At a higher level of InfoRDS, the number of start sets which are discarded because of wrong signatures are also shown. Now the cosets are changed. Here we use the NoSort version of ExtendedStartsets. This leads to a lot of start sets in the first step. If the number of start sets in U is very large, this could be too much for a reduction. Then the only option is using the brute force method. But also for the brute force search, ExtendedStartSetsNoSort must be called first (remember that we chos an enumeration of G and assume the last element from each startset to be the largeset ``interesting'' one for further completions).

gap> comps:=Difference(GroupList2PermList(Set(U1),Gdata),Np);;
gap> ssets:=ExtendedStartsetsNoSort(ssets,comps,Np,11,Gdata);;
gap> ssets:=ReducedStartsets(ssets,[Gdata.Aac],sigdat,Gdata.diffTable);; 
#I  Size 8640
#I  9/ 0 @ 0:00:14.159
gap> Size(ssets);  
6899
And as above, we continue:
repeat 
    ssets:=ExtendedStartsets(ssets,comps,Np,11,Gdata); 
    ssets:=ReducedStartsets(ssets,[Gdata.Aac],sigdat,Gdata.diffTable);; 
until ssets=[] or Size(ssets[1])=11; 
comps:=Difference(GroupList2PermList(Set(U2),Gdata),Np); 
RaiseStartSetLevelNoSort(ssets,comps,Np,15,Gdata); 
repeat 
    ssets:=ExtendedStartsets(ssets,comps,Np,15,Gdata); 
    ssets:=ReducedStartsets(ssets,[Gdata.Aac],sigdat,Gdata.diffTable);; 
until ssets=[] or Size(ssets[1])=15; 

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

RDS manual
February 2012