example.tex

\Chapter{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 \cite{DembowskiPiper}, \cite{Dembowski}
or \cite{RoederDiss} for details.

To have a little more output, you may want to increase "InfoRDS":
\begintt
gap> SetInfoLevel(InfoRDS,3);
\endtt

First, define some parameters and calculate the data needed:
\beginexample
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);; 
\endexample

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.

\beginexample
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]);;
\endexample

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

\beginexample
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 ] ] ]
\endexample

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.
%notest
\beginexample
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 ] ]
\endexample

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$.
%notest
\beginexample
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
\endexample
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).

%notest
\beginexample
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
\endexample
%
And as above, we continue:
%
\begintt
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; 
\endtt

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%E