1 #include "defs.h"
2 #include "permfns.h"
3
4 extern char cent,sym,hgst,nop,nonb[],inf1[],inf2[],inf3[],outf1[],
5 outf2[];
6 extern short mp,mexp,mb,mnpt,prime,
7 perm[],sv[],cp[],orb[],gbase[],hbase[],obase[],
8 nbase[],lorbg[],lorbn[],lorbh[],ntno[],reg[],endorno[],
9 ntorno[], tsv1[],tsv2[],tsv3[],genorb[],expcp[],
10 fp[],pno[],start[],space[],ipno[],
11 *pptr[],*svgptr[],*svhptr[],*svnptr[],*intorb[],
12 *horno[],*hlorb[],*expptr[],*imorno[],
13 *imlorb[],*orbperm[],*deftime[],*regsv[];
14 extern int sp,svsp;
15
16 extern short npt,npt1,nptd2,nbg,nbh,stg,sth,nf,nrego,nnth,lnth,nhorbs,ad1,
17 hgno,lexp,*norsh,*norsim,*defim,*orlist,*imhno,*inim,fsth,*adpt,*bindor,
18 *reginfo,*test;
19 short adno,gskno,nskno,orhct,ntct,ontct,oorhct,onf,
20 *sva,*ap,stn,*tp,*itp,nnps;
21 char fail,bt,biggersylp,type[14];
22
23 extern FILE *ip,*op;
24
err(void)25 void err (void) { fprintf(stderr,"Out of space. Increase PSP (or MP).\n");}
26
clrop(void)27 int clrop (void)
28 /* Clears and updates orbit permutation info */
29 { short i,j,k,l;
30 for (i=1;i<=nhorbs;i++)
31 { l= *hlorb[i];
32 for (j=1;j<=l;j++)
33 { k=orbperm[i][j];
34 if (k!=0 && deftime[i][k]>=adno)
35 { deftime[i][k]=0; orbperm[i][j]=0; }
36 }
37 }
38 return(0);
39 }
40
bind(int pno)41 void bind (int pno)
42 /* Adds a permutation in H or a newly found one in N (=N(H)) to those
43 generating the orbit of gbase[gskno]. These orbit points need not be
44 considered as images of new elements.
45 */
46 { short i,j,k,l,m,n;
47 for (i=1;i<=npt;i++)
48 { j=pptr[pno][i]; k=bindor[i]; l=bindor[j];
49 if (k!=l)
50 { if (k>l) { m=k;k=l;l=m;}
51 for (n=1;n<=npt;n++) if (bindor[n]==l) bindor[n]=k;
52 }
53 }
54 }
55
56 int
setskno(void)57 setskno (void)
58 /* Preliminary processing done for a new value of gskno. */
59 { short i,j,k,n,*p;
60 /* if reg[adno]>0, we need not consider this as gskno */
61 while (reg[adno]>0)
62 { adno-=1; inim[gbase[adno]]=0; clrop(); }
63 /* Remember initial values of orhct and oorhct. These are recalled after we
64 find a new generator in N(H).
65 */
66 oorhct=orhct; ontct=ntct; *expcp=1; gskno=adno;
67 /* Set up info needed for running thro elements in search list. */
68 if (sym)
69 { bt=1;
70 for (i=1;bt;i++) if (inim[i]==0 && i!=gbase[adno]) { bt=0; expcp[1]=i; }
71 bt=1;
72 for (i=npt;bt;i--) if (inim[i]==0 && i!=gbase[adno])
73 { bt=0; start[adno+1]=i; }
74 }
75 else
76 { expcp[1]=start[adno]+1;
77 if (adno<=lexp)
78 { sva=svgptr[adno]; ap=adpt+adno; *ap=1;
79 while (sva[*ap]<=0) (*ap)++;
80 exprep(*ap,adno,sva);
81 }
82 }
83 *pno=0;
84 if (ntorno[adno] > 0)
85 { p=imlorb[orhct]; for (j=1;j<= *p;j++) p[j]=abs(p[j]); }
86 /* Initialize the "bound" orbit, using bind, as above, and add the relevant
87 elements of H to the generators of N.
88 */
89 for (i=1;i<=npt;i++) bindor[i]=i; bindor[gbase[gskno]]=0;
90 for (i=stn;i!= -1;i=fp[i]) {bind(i); (*pno)++; pno[*pno]=i; n=i; }
91 k=ntno[adno];
92 if (k!=0)
93 { for (i=sth;i!= -1;i=fp[i]) if (pptr[i][npt1]==k)
94 { if (nf== -1) { err(); return(-1); }
95 for (j=1;j<=npt+npt1;j++) pptr[nf][j]=pptr[i][j];
96 pptr[nf][npt1]=nskno;
97 (*pno)++; pno[*pno]=nf;
98 if (stn== -1) stn=nf; else fp[n]=nf;
99 bind(nf); n=nf; nf=fp[nf];
100 } fp[n]= -1;
101 }
102 lorbn[nskno]=orbitsv(nbase[nskno],svnptr[nskno],0);
103 printf("gskno=%d, nskno=%d.\n",gskno,nskno); tp[npt1]=nskno;
104 return(0);
105 }
106
107 int
found(void)108 found (void)
109 /* Processing required on finding a new generator of N. */
110 { short i,j,k,*ptr,olo;
111 *pno=0;
112 for (i=stn;i!= -1;i=fp[i]) {(*pno)++; pno[*pno]=i; j=i; }
113 if (stn== -1) stn=onf; else fp[j]=onf;
114 (*pno)++; pno[*pno]=onf;
115 j= (ntorno[gskno]>0 || gskno>lnth) ? oorhct+1 : oorhct;
116 for (i=j;i<=orhct;i++)
117 { ptr=imlorb[i]; for (k=1;k<= *ptr;k++) ptr[k]=abs(ptr[k]);}
118 orhct=oorhct; ntct=ontct;
119 fp[onf]= -1; bind(onf);
120 if (nop)
121 { tp[npt+1]=1; printvec(tp,1); tp[npt+1]=nskno;}
122 olo=lorbn[nskno];
123 lorbn[nskno]=orbitsv(nbase[nskno],svnptr[nskno],0);
124 if (prime==0) biggersylp=0;
125 else biggersylp = ((lorbn[nskno]/olo)%prime == 0);
126 onf=nf; if (onf== -1) {err(); return(-1); }
127 nf=fp[nf]; tp=pptr[onf]; itp=tp+npt1;
128 for (i=1;i<gskno;i++) tp[gbase[i]]=gbase[i]; tp[npt1]=nskno;
129 *expcp=1; adno=gskno;
130 if (sym)
131 { for (i=1;i<=npt;i++) inim[i]=0; for (i=1;i<adno;i++) inim[gbase[i]]=1;}
132 if (cent) strcpy(type,"centralizer"); else strcpy(type,"normalizer");
133 printf("Found element in %s. lorb=%3d.\n",type,lorbn[nskno]);
134 nnps++;
135 return(0);
136 }
137
138 int
deforbperm(int bpt,int imbpt)139 deforbperm (int bpt, int imbpt)
140 /* Update orbit permutation information using fact that tp[bpt]=imbpt. */
141 { short i,x,y,z;
142 for (i=1;fail==0 && i<=orhct;i++)
143 { x=horno[i][bpt]; y=imorno[i][imbpt]; z=orbperm[i][x];
144 if (z==0)
145 { if (deftime[i][y]==0)
146 { if (hlorb[i][x]==abs(imlorb[i][y]))
147 { orbperm[i][x]=y; deftime[i][y]=adno; }
148 else fail=1;
149 } else fail=1;
150 } else if (z!=y) fail=1;
151 }
152 }
153
154 int
nprg2(void)155 nprg2 (void)
156 { short nbn,i,j,k,l,m,n,bpt,imbpt,ct,endo,*ptr;
157 char hornt,complete,advance,bt,orhad;
158 int quot;
159 nnps=0; stn= -1; nbn=0;
160 /* Compute a largest possible basis of N */
161 for (i=1;i<=nbg;i++) if (reg[i]<=0)
162 { nbn++;
163 if (nbn>mb)
164 { fprintf(stderr,"Too many N-base points. Increase MB.\n"); return(-1);}
165 nbase[nbn]=gbase[i];
166 }
167 printf("nbn=%d.\n",nbn);
168 k= (sym) ? mb : lexp+mb; quot=svsp/npt-k;
169 if ((sym==0) && *obase>nbn) m= *obase; else m=nbn;
170 if (quot<m)
171 { fprintf(stderr,"svsp too small. Increase SVSP.\n"); return(-1); }
172 ptr = (sym) ? sv-1 : sv+lexp*npt-1;
173 for (i=1;i<=m+mb;i++) {svnptr[i]=ptr; ptr+=npt; }
174 if (sym) for (i=1;i<=npt;i++) inim[i]=0;
175
176 /* During the main search, we attempt to construct a permutation tp, which we
177 hope will lie in N(H). For each base point in turn, bpt=gbase[adno], we
178 consider the image imbpt=tp[bpt], and subject it to various tests. If it
179 fails any test, then the flag fail becomes true, and this image is known to
180 be impossible, so we attempt to alter this image, without changing
181 tp[gbase[i]] for i<adno. If impossible, we backtrack, and reduce adno.
182 gskno is the G-base no for which we are currently searching in G[gskno], and
183 nskno the corresponding N-base no.o
184 orhct and ntct are approximately the values of orhno and ntno for the
185 current adno. First we initialize everything.
186 */
187 n=0; ntct=0; orhct=0;
188 for (i=1;i<nbg;i++)
189 { if (ntorno[i] > 0) orhct++; if (ntno[i]>0) ntct++;
190 /* regsv is used when we compute automorphism actions of tp on O, as described
191 in normp1.c
192 */
193 if (reg[i]<0 && ntno[i]>0)
194 {n++; /* for (j=1;j<=npt;j++) regsv[n][j]=svhptr[ntct][j]; */
195 regsv[n]=svhptr[ntct];
196 }
197 k=gbase[i];
198 for (j=1;j<=orhct;j++)
199 { l=horno[j][k];
200 if (deftime[j][l]==0) { orbperm[j][l]=l; deftime[j][l]=i; }
201 }
202 inim[k]=1;
203 }
204 if (ntorno[nbg] > 0 || cent) {orhct++; ntct++; }
205 adno=nbg; nskno=nbn;
206 onf=nf; nf=fp[nf];
207 if (onf== -1) {err(); return(-1); }
208 tp=pptr[onf]; itp=tp+npt1;
209 for (i=1;i<nbg;i++) tp[gbase[i]]=gbase[i]; tp[npt1]=nskno;
210
211 printf("\nBeginning main search.\n");
212 if (setskno()== -1) return(-1);
213 if (nop) { op=fopen(outf2,"w");fprintf(op," \n"); }
214 complete=0;
215 /* The main search loop follows. */
216 while (complete==0)
217 { bpt=gbase[adno]; imbpt= (sym) ? expcp[*expcp] : expimage(bpt);
218 tp[bpt]=imbpt; hornt= (ntorno[adno]>0);
219 fail=0; advance=0; orhad=0;
220 if (adno==gskno) { if (bindor[imbpt]==0) fail=1; }
221 /* Fails since imbpt is already in image of N */
222 else if (hornt) { if (imlorb[orhct][imorno[orhct][imbpt]]<0) fail=1; }
223 /* Fails since this orbit has already been ruled out as a possible image. */
224 if (reg[adno]>0 && imbpt!=defim[adno]) fail=1;
225 /* defim[adno] is the value of tp[bpt] which is forced by earlier values of
226 tp, and automorphism information computed earlier from reginfo.
227 */
228 if (fail==0) deforbperm(bpt,imbpt);
229 /* If orbits are not permuted, deforbperm sets fail=1 */
230 if (fail==0 && ntorno[adno]<0)
231 /* Now if ntorno[adno]<0 we check that the image of O1 has kernel at least
232 as big as that of the image of O.
233 */
234 { n= -ntorno[adno]-1; m= (n==0) ? 0 : ntorno[n];
235 if (m>0)
236 { l=imorno[m][imbpt]; ct=0;
237 for (i=1;i<=npt;i++) if (imorno[m][i]==l) {ct++; orlist[ct]=i;}
238 i=sth;
239 while (pptr[i][npt1]>ntct)
240 { for (j=1;j<=ct;j++) {k=orlist[j]; if (pptr[i][k]!=k) fail=1; }
241 i=fp[i];
242 }
243 }
244 }
245 if (fail==0 && hornt)
246 /* In case adno corresponds to an H-base point, we now change the hbase[adno]
247 to imbpt, and compute stabilizer orbits, as imorno,imlorb. If these do
248 not correspond to the originals in H, then fail becomes true.
249 Eventually they will be the images of the H orbits.
250 */
251 { if (intbase(imbpt,ntct,&sth,&nbh,hbase,lorbh,svhptr)== -1) return(-1);
252 if (orhct<nhorbs)
253 { orhct++; orhad=1; *pno=0; i=sth;
254 while (pptr[i][npt1]>ntct) { (*pno)++; pno[*pno]=i; i=fp[i]; }
255 allorbs(test,imorno[orhct]); ptr=hlorb[orhct];
256 if (*ptr != *test) {fail=1; orhct--; }
257 else
258 { for (j=1;j<=nptd2;j++) {norsh[j]=0; norsim[j]=0; }
259 l=0; m=0;
260 for (j=1;j<= *ptr;j++)
261 { if (*(ptr+j)>nptd2) l= *(ptr+j); else norsh[*(ptr+j)]++;
262 if (*(test+j)>nptd2) m= *(test+j); else norsim[*(test+j)]++;
263 }
264 fail = (l!=m);
265 for (i=1;fail==0 && i<=nptd2;i++) fail= (norsh[i]!=norsim[i]);
266 if (fail) orhct--;
267 else for (i=0;i<= *test;i++) imlorb[orhct][i]=test[i];
268 }
269 }
270 if (fail==0 && reg[adno]<0)
271 /* If reg[adno]<0, we compute the corresponding F in the image, which must
272 have the same size as the original F.
273 */
274 { n=ntorno[adno]; m=imorno[n][imbpt]; ct=0; l= -reg[adno+1];
275 bt= (n==nhorbs);
276 for (i=1;i<=npt;i++) if (imorno[n][i]==m)
277 if (bt || imlorb[n+1][imorno[n+1][i]]==1) { ct++;orlist[ct]=i; }
278 if (ct!=l) fail=1;
279 /* *pno=0; bt= (fail==0); i=sth;
280 while (bt)
281 { if (i== -1) bt=0; else
282 { j=pptr[i][npt1]; if (j>=ntct) {(*pno)++; pno[*pno]=i; }
283 else if (j<ntct) bt=0; i=fp[i];
284 }
285 }
286 if (fail==0) { i= -reg[adno]; orbitsv(imbpt,regsv[i],0); }
287 */
288 if (fail && orhad) orhct--;
289 }
290 }
291 if (fail==0 && (endo=endorno[adno])>0)
292 /* if adno completes the orbit O, we compute the images of the relevant section
293 of H on O, using the copies of the generators of H that we made at the end
294 of nprg1(). These will be used to compute the images on corresponding orbits
295 O1.
296 */
297 { if (sym==0) for (i=1;i<=npt;i++) tp[i]=expimage(i);
298 i=fsth;
299 while (pptr[i][npt1]>ntct) i=fp[i];
300 while (i!= -1)
301 { *cp=0;
302 for (j=endo;fail==0 && j<=adno;j++)
303 { l=ntno[j]; m=image(tp[pptr[i][gbase[j]]]);
304 if (l>0) { if (svhptr[l][m]!=0) addsv(m,svhptr[l]); else fail=1; }
305 else if (m!=tp[gbase[j]]) fail=1;
306 }
307 if (fail) i= -1; else
308 { k=i+1;
309 for (j=1;j<=npt;j++) pptr[k][j]=backimage(j);
310 i=fp[i];
311 if (i!= -1 && pptr[i][npt1]<ntno[endo]) i= -1;
312 }
313 }
314 if (fail && orhad) orhct--;
315 }
316 if (fail==0)
317 /* tp has passed all tests for this adno, so we increase adno. If adno=nbg,
318 we are ready to compute tp in full, and see if it really lies in N(H).
319 */
320 { inim[imbpt]=1; adno++;
321 if (adno<=nbg)
322 { advance=1;
323 if (reg[adno]>0)
324 /* if reg[adno]>0 we can compute defim[gbase[adno]] using info already computed,
325 and stored in reginfo.
326 */
327 { n=reg[adno]; m=reginfo[n];
328 if (m>0)
329 /* Case 1: gbase[adno] in set F in orbit O. */
330 { l= -reg[m]; n++; ct=reginfo[n]; *cp=0;
331 for (i=1;i<=ct;i++) {n++; addsv(tp[reginfo[n]],regsv[l]);}
332 defim[adno]=image(tp[gbase[m]]);
333 }
334 else
335 /* Case 2: gbase[adno] in an orbit O1. */
336 { n++; *cp=reginfo[n];
337 for (k=1;k<= *cp;k++) cp[k]=reginfo[n+(*cp)+1-k];
338 defim[adno]=image(tp[-m]);
339 }
340 }
341 if (sym)
342 { bt=1;
343 for (i=npt;bt;i--) if (inim[i]==0) {start[adno+1]=i;bt=0;}
344 bt=1;
345 if (reg[adno]>0)
346 { k=defim[adno];
347 if (inim[k]) { adno--; if (orhad) orhct--; advance=0; fail=1;}
348 else {(*expcp)++; expcp[*expcp]=k; }
349 }
350 else for (i=1;bt;i++) if (inim[i]==0)
351 { (*expcp)++; expcp[*expcp]=i; bt=0; }
352 }
353 }
354 else
355 /* Compute tp, checking with deforbperm as we go. */
356 { for (i=1; fail==0 && i<=npt;i++) if (nonb[i])
357 { if (sym)
358 { for (k=1;k<=npt;k++) if (inim[k]==0) {j=k; tp[i]=k; } }
359 else {j=expimage(i); tp[i]=j; }
360 deforbperm(i,j);
361 }
362 if (fail==0)
363 { invert(tp,itp);
364 /* See if it lies in N(H) (or C(H)) */
365 i = (hgst) ? 0 : sth;
366 while (i!= -1 && fail==0)
367 { if (cent)
368 { for (j=1;fail==0 && j<=npt;j++)
369 if (tp[pptr[i][itp[j]]] != pptr[i][j]) fail=1;
370 } else
371 { *cp=0; for (j=1;fail==0 && j<=nbg;j++)
372 { k=image(tp[pptr[i][gbase[j]]]); l=ntno[j];
373 if (l!=0)
374 { if (svhptr[l][k]!=0) addsv(k,svhptr[l]); else fail=1; }
375 else if (k!=tp[gbase[j]]) fail=1;
376 }
377 }
378 if (hgst) {i++; if (i==hgno) i= -1;} else i=fp[i];
379 }
380 }
381 if (fail) adno--;
382 else
383 { if (found()== -1) return(-1);
384 if (biggersylp) {ad1=gskno; break;}
385 }
386 }
387 }
388 if (advance)
389 /* Change tp, changing image at current value of adno if possible. */
390 { if (ntno[adno]>0) ntct++; if (adno<=lexp) adpt[adno]=0; }
391 else
392 { bt=1;
393 while (bt)
394 { imbpt=tp[gbase[adno]];
395 if (fail) { m=ntorno[adno]; if (m>0) n=imorno[orhct][imbpt]; }
396 if (reg[adno]<=0 || defim[adno]!=imbpt)
397 if (sym==0)
398 { if (expcp[*expcp]<=start[adno])
399 { (*expcp)++; expcp[*expcp]=start[adno]+1; bt=0; }
400 else if (adno>lexp && expcp[*expcp]<start[adno+1])
401 { expcp[*expcp]++; bt=0; }
402 if (adno<=lexp)
403 { sva=svgptr[adno]; ap=adpt+adno; (*ap)++;
404 while (sva[*ap]<=0 && *ap<=npt) (*ap)++;
405 if (*ap<=npt) {bt=0; exprep(*ap,adno,sva); } else bt=1;
406 }
407 }
408 else if (expcp[*expcp]<start[adno+1])
409 { j=expcp[*expcp]; inim[j]=0;
410 for (i=j+1;bt;i++)
411 if (inim[i]==0 && (adno!=gskno || i!=gbase[adno]))
412 { expcp[*expcp]=i; bt=0; }
413 }
414 if (bt)
415 { j=ntorno[adno];
416 if (j>0)
417 { ptr=imlorb[orhct];
418 for (k=1;k<= *ptr;k++) ptr[k]=abs(ptr[k]); ntct--;
419 }
420 if (sym) { inim[expcp[*expcp]]=0; (*expcp)--; }
421 else if (expcp[*expcp]>start[adno]) (*expcp)--;
422 adno--;
423 if (adno==0) bt=0;
424 else
425 { if (ntorno[adno]>0 && adno!=lnth) orhct--;
426 if (*expcp==0) bt=0;
427 }
428 }
429 }
430 clrop();
431 if (*expcp==0)
432 { if (adno<ad1) {complete=1; printf("Algorithm complete.\n");}
433 else
434 { inim[gbase[adno]]=0; nskno--;
435 if (setskno()== -1) return(-1);
436 }
437 }
438 else if (fail)
439 { if (adno==gskno)
440 { k=bindor[imbpt];
441 for (i=1;i<=npt;i++) if (bindor[i]==k) bindor[i]=0;
442 }
443 else if (m>0) imlorb[m][n]= -abs(imlorb[m][n]);
444 }
445 }
446 } /* Main search loop */
447
448 /* End of search. Add any remaining generators to N, change back to old
449 base if necessary, and output.
450 */
451 if (cent==0)
452 { *pno=0;
453 for (i=stn;i!= -1;i=fp[i]) {(*pno)++; pno[*pno]=i; n=i;}
454 for (m=ad1-1;m>=1;m--)
455 { k=ntno[m];
456 if (k!=0)
457 { for (i=sth;i!= -1;i=fp[i]) if (pptr[i][npt1]==k)
458 { if (nf== -1) {err(); return(-1); }
459 for (j=1;j<=npt+npt1;j++) pptr[nf][j]=pptr[i][j]; pptr[nf][npt1]=m;
460 (*pno)++; pno[*pno]=nf;
461 if (stn== -1) stn=nf; else fp[n]=nf;
462 n=nf; nf=fp[nf];
463 } fp[n]= -1;
464 }
465 lorbn[m]=orbitsv(nbase[m],svnptr[m],0);
466 }
467 }
468 if (nop)
469 { fclose(op);
470 if (nnps==0) unlink(outf2);
471 else
472 { op=fopen(outf2,"r+"); fprintf(op,"%4d%4d%4d%4d",npt,nnps,0,0);
473 fclose(op);
474 }
475 }
476 if (sym==0) for (i=1;i<= *obase;i++)
477 if (intbase(obase[i],i,&stn,&nbn,nbase,lorbn,svnptr) == -1) return(-1);
478 bt=1;
479 for (i=1;i<=nbn;i++) if (lorbg[i]!=lorbn[i]) {bt=0; break;}
480 *pno=0;
481 for (i=stn;i!= -1;i=fp[i]) {(*pno)++; pno[*pno]=i; }
482 if (*pno==0) {printf("Group is trivial.\n"); return(-1); }
483 op=fopen(outf1,"w");
484 fprintf(op,"%4d%4d%4d%4d\n",npt,*pno,nbn,3);
485 printbaselo(nbn,nbase,lorbn); printpsv(nbn,pno,svnptr);
486 fclose(op);
487 return(0);
488 }
489