[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