| Quellcodebibliothek Statistik Leitseite products/sources/formale Sprachen/GAP/pkg/rds/doc/ (Algebra von RWTH Aachen Version 4.15.1©) Datei vom 24.8.2025 mit Größe 5 kB |
|
Quelle example.tex Sprache: Latech |
|||||||||
|
\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 ¤ Dauer der Verarbeitung: 0.12 Sekunden (vorverarbeitet) ¤*© Formatika GbR, Deutschland |
|
2026-03-28