1 /****************************************************************************
2 **
3 *A standard.c ANUPQ source Eamonn O'Brien
4 **
5 *Y Copyright 1995-2001, Lehrstuhl D fuer Mathematik, RWTH Aachen, Germany
6 *Y Copyright 1995-2001, School of Mathematical Sciences, ANU, Australia
7 **
8 */
9
10 #include "pq_defs.h"
11 #include "constants.h"
12 #include "pcp_vars.h"
13 #include "pga_vars.h"
14 #include "exp_vars.h"
15 #include "constants.h"
16 #include "pq_functions.h"
17 #include "menus.h"
18 #include "standard.h"
19
20 #if defined(GROUP) && defined(STANDARD_PCP)
21
22 static int map_array_size;
23 static int output;
24
25 static void enforce_exp_law(struct pcp_vars *pcp);
26 static int **start_pga_run(Logical *identity_map,
27 int ***auts,
28 struct pga_vars *pga,
29 struct pcp_vars *pcp);
30 static int **
31 group_completed(int ***auts, struct pga_vars *pga, struct pcp_vars *pcp);
32 static int **finish_pga_run(Logical *identity_map,
33 FILE *cover_tmp_file,
34 FILE *group_file,
35 int ***auts,
36 struct pga_vars *pga,
37 struct pcp_vars *pcp);
38 static int **find_stabiliser(Logical *identity_map,
39 int non_standard,
40 int ***auts,
41 int **perms,
42 int *a,
43 int *b,
44 char *c,
45 int *orbit_length,
46 struct pga_vars *pga,
47 struct pcp_vars *pcp);
48 static void
49 trace(char *word_map, int *depth, int label, int *backptr, char *schreier);
50 static char *find_word(int *word_length,
51 Logical soluble_group,
52 int **perms,
53 int rep,
54 int non_standard,
55 int orbit_length,
56 int *b,
57 char *c,
58 struct pga_vars *pga);
59 static int **standard_map(char *word_map,
60 int word_length,
61 Logical *identity_map,
62 int rep,
63 int ***auts,
64 struct pga_vars *pga,
65 struct pcp_vars *pcp);
66 static int inverse_image(int l, int *perms, struct pga_vars *pga);
67 static void list_subgroup(int rep, struct pga_vars *pga, struct pcp_vars *pcp);
68
69 /* compute a standard presentation for a group;
70
71 this procedure assumes that
72 -- an arbitary finite presentation has been
73 supplied;
74 -- a standard presentation has been computed
75 for the class c p-quotient;
76 -- a presentation for the p-covering group
77 computed using this standard presentation has
78 been set up before the call to this procedure;
79
80 we will now compute the standard presentation for the
81 class c + 1 p-quotient */
82
standard_presentation(Logical * identity_map,int standard_output,int *** auts,struct pga_vars * pga,struct pcp_vars * pcp)83 void standard_presentation(Logical *identity_map,
84 int standard_output,
85 int ***auts,
86 struct pga_vars *pga,
87 struct pcp_vars *pcp)
88 {
89 int i;
90 int **map;
91 #if defined(TIME)
92 int t;
93 #endif
94
95 output = standard_output;
96
97 #if defined(TIME)
98 t = runTime();
99 #endif
100
101 map = start_pga_run(identity_map, auts, pga, pcp);
102 if (map == NULL)
103 return;
104
105 #if defined(TIME)
106 printf("time in start_pga is %.2f\n", (runTime() - t) * CLK_SCALE);
107 #endif
108
109 if (output == MAX_STANDARD_PRINT) {
110 printf("The standard automorphism is:\n");
111 for (i = 1; i <= pga->ndgen; ++i) {
112 printf("%d ---> ", i);
113 print_array(map[i], 1, pcp->lastg + 1);
114 }
115 }
116
117 #if defined(DEBUG)
118 printf("Map identity? %d\n", *identity_map);
119 #endif
120
121 map_relations(map, pga, pcp);
122
123 /* memory leakage September 1996 -- originally pcp->lastg */
124 free_matrix(map, map_array_size, 1);
125 }
126
127 /* enforce the exponent law, if any, on the group */
128
enforce_exp_law(struct pcp_vars * pcp)129 static void enforce_exp_law(struct pcp_vars *pcp)
130 {
131 register int *y = y_address;
132
133 struct exp_vars exp_flag;
134
135 if (pcp->extra_relations != 0) {
136
137 initialise_exponent(&exp_flag, pcp);
138
139 extra_relations(&exp_flag, pcp);
140
141 /* are there redundant defining generators? if so, be careful
142 about elimination -- see next_class for further information */
143
144 if (pcp->ndgen > y[pcp->clend + 1])
145 eliminate(TRUE, pcp);
146 else
147 eliminate(FALSE, pcp);
148 }
149 }
150
151 /* commence a partial run of p-group generation in order
152 to determine the standard presentation for this class */
153
start_pga_run(Logical * identity_map,int *** auts,struct pga_vars * pga,struct pcp_vars * pcp)154 static int **start_pga_run(Logical *identity_map,
155 int ***auts,
156 struct pga_vars *pga,
157 struct pcp_vars *pcp)
158 {
159 FILE *cover_file; /* store complete p-cover of group */
160 FILE *cover_tmp_file; /* store (reduced) p-cover of group */
161 FILE *group_file; /* store class c + 1 quotient of group */
162 int **map; /* automorphism to apply to presentation */
163 #if defined(TIME)
164 int t = runTime();
165 #endif
166
167 /* save (reduced) p-covering group presentation to temporary file */
168 cover_tmp_file = TemporaryFile();
169 save_pcp(cover_tmp_file, pcp);
170 RESET(cover_tmp_file);
171
172 /* we need compute the class c + 1 quotient only on the first
173 time through or if the map applied to the previous presentation
174 was not the identity; in these cases, before
175 computing class c + 1 quotient, restore complete p-cover;
176 we cannot use the reduced p-cover because a presentation having
177 redundant generators can cause difficulties with interaction
178 between update_generators and eliminate */
179
180 if (*identity_map == FALSE) {
181
182 cover_file = OpenFile("ISOM_cover_file", "r");
183 restore_pcp(cover_file, pcp);
184 CloseFile(cover_file);
185
186 /* enforce exponent law on complete p-cover */
187 enforce_exp_law(pcp);
188
189 /* now compute the presentation for the class c + 1 quotient */
190 pcp->multiplicator = FALSE;
191 update_generators(pcp);
192
193 collect_relations(pcp);
194
195 eliminate(FALSE, pcp);
196 if (pcp->overflow || !pcp->valid)
197 exit(FAILURE);
198
199 /* when relations are enforced, the group may complete */
200 if (pcp->complete) {
201 map = group_completed(auts, pga, pcp);
202 *identity_map = TRUE;
203 CloseFile(cover_tmp_file);
204 return map;
205 }
206
207 /* save presentation for class c + 1 quotient to file */
208 group_file = OpenFile("ISOM_group_file", "w+");
209 save_pcp(group_file, pcp);
210 } else {
211 /* we must restore the presentation to correctly determine step size */
212 group_file = OpenFile("ISOM_group_file", "r");
213 restore_pcp(group_file, pcp);
214 }
215
216 RESET(group_file);
217
218 #if defined(TIME)
219 t = runTime() - t;
220 printf("Time to compute class c + 1 is %.2f seconds\n", t * CLK_SCALE);
221 #endif
222
223 /* note step size required for p-group generation */
224 pga->step_size = pcp->lastg - pcp->ccbeg + 1;
225
226 map =
227 finish_pga_run(identity_map, cover_tmp_file, group_file, auts, pga, pcp);
228 CloseFile(group_file);
229 CloseFile(cover_tmp_file);
230
231 return map;
232 }
233
234 /* the group has completed when the relations are imposed; we write
235 necessary files in order to have consistent behaviour pattern */
236
237 static int **
group_completed(int *** auts,struct pga_vars * pga,struct pcp_vars * pcp)238 group_completed(int ***auts, struct pga_vars *pga, struct pcp_vars *pcp)
239 {
240 FILE *NextClass;
241 FILE *Status;
242 int i, j, k;
243 int **standard;
244
245 NextClass = OpenFile("ISOM_NextClass", "w+");
246
247 fprintf(NextClass, "%d\n", pga->m);
248 fprintf(NextClass, "%d\n", pcp->lastg);
249 for (i = 1; i <= pga->m; ++i) {
250 for (j = 1; j <= pga->ndgen; ++j) {
251 for (k = 1; k <= pcp->lastg; ++k)
252 fprintf(NextClass, "%d ", auts[i][j][k]);
253 fprintf(NextClass, "\n");
254 }
255 }
256
257 fprintf(NextClass, "%d\n", pga->fixed);
258 fprintf(NextClass, "%d\n", pga->soluble);
259 #ifdef HAVE_GMP
260 mpz_out_str(NextClass, 10, &pga->aut_order);
261 fprintf(NextClass, "\n");
262 #endif
263 CloseFile(NextClass);
264
265 Status = OpenFile("ISOM_Status", "w");
266 fprintf(Status, "%d ", END_OF_CLASS);
267 fprintf(Status, "%d ", TERMINAL);
268 CloseFile(Status);
269
270 map_array_size = pcp->lastg;
271 standard = allocate_matrix(pcp->lastg, pcp->lastg, 1, FALSE);
272
273 for (i = 1; i <= pga->ndgen; ++i)
274 for (j = 1; j <= pcp->lastg; ++j)
275 standard[i][j] = (i == j) ? 1 : 0;
276
277 return standard;
278 }
279
280 /* complete pga run to compute standard presentation for this class */
281
finish_pga_run(Logical * identity_map,FILE * cover_tmp_file,FILE * group_file,int *** auts,struct pga_vars * pga,struct pcp_vars * pcp)282 static int **finish_pga_run(Logical *identity_map,
283 FILE *cover_tmp_file,
284 FILE *group_file,
285 int ***auts,
286 struct pga_vars *pga,
287 struct pcp_vars *pcp)
288 {
289 int **perms;
290
291 FILE *LINK_input;
292 int k;
293 int upper_step;
294 Logical soluble_group;
295 #if defined(GAP_LINK)
296 Logical process_fork = FALSE; /* has GAP process forked? */
297 #endif
298 int *a;
299 int *b;
300 char *c;
301 int *orbit_length;
302 int **subgroup_matrix;
303 int K; /* bit string representation of definition set */
304 int *subset; /* definition set */
305 int non_standard; /* label for allowable subgroup defining
306 non-standard presentation */
307 int **map; /* automorphism to apply to presentation */
308 #if defined(TIME)
309 int t;
310 #endif
311 char *s;
312
313 restore_pcp(cover_tmp_file, pcp);
314 RESET(cover_tmp_file);
315
316 #if defined(DEBUG)
317 printf("Now restore p-covering group\n");
318 print_presentation(FALSE, pcp);
319 #endif
320
321 pga->exponent_law = pcp->extra_relations;
322 /*
323 enforce_laws (pga, pga, pcp);
324 */
325 extend_automorphisms(auts, pga->m, pcp);
326
327 /* critical */
328 /*
329 read_subgroup_rank (&k);
330 */
331
332 /* if you want something other than default, change value of k */
333 k = 0;
334 step_range(k, &pga->s, &upper_step, auts, pga, pcp);
335
336 if (pga->s != upper_step) {
337 pga->s = upper_step;
338
339 /* first, find the valid relative step size, pga->s */
340 find_allowable_subgroup(
341 RELATIVE, cover_tmp_file, group_file, &K, &subset, pga, pcp);
342 }
343
344 /* now find allowable subgroup which determines the class c + 1 quotient */
345 subgroup_matrix = find_allowable_subgroup(
346 2, cover_tmp_file, group_file, &K, &subset, pga, pcp);
347
348 restore_pcp(cover_tmp_file, pcp);
349 RESET(cover_tmp_file);
350
351 #if defined(DEBUG)
352 printf("Now restore p-covering group\n");
353 print_presentation(FALSE, pcp);
354 #endif
355
356 #if defined(DEBUG)
357 printf("Rank of characteristic subgroup is %d\n", pga->q);
358 #endif
359
360 store_definition_sets(pga->r, pga->s, pga->s, pga);
361 get_definition_sets(pga);
362
363 #if defined(DEBUG)
364 pga->print_degree = TRUE;
365 #endif
366 compute_degree(pga);
367 pga->print_degree = FALSE;
368
369 non_standard = subgroup_to_label(subgroup_matrix, K, subset, pga);
370
371 /* memory leakage September 1996 */
372 free_vector(subset, 0);
373 free_matrix(subgroup_matrix, pga->s, 0);
374
375 if (output == MAX_STANDARD_PRINT) {
376 printf("Non-standard label is %d\n", non_standard);
377 printf("Required step size is %d\n", pga->step_size);
378 printf("Relative step size is %d\n", pga->s);
379 printf("Rank of characteristic subgroup is %d\n", pga->q);
380 }
381
382 strip_identities(auts, pga, pcp);
383 soluble_group = (pga->soluble || pga->Degree == 1 || pga->nmr_of_perms == 0);
384
385 if (!soluble_group) {
386 #if defined(GAP_LINK)
387 if (!process_fork) {
388 start_GAP_file(auts, pga, pcp);
389 process_fork = TRUE;
390 }
391 StartGapFile(pga);
392 #elif defined(GAP_LINK_VIA_FILE)
393 start_GAP_file(&LINK_input, auts, pga, pcp);
394 #endif
395 }
396
397 #if defined(DEBUG)
398 /*
399 pga->print_permutation = TRUE;
400 */
401 #endif
402
403 #if defined(TIME)
404 t = runTime();
405 #endif
406
407 perms = permute_subgroups(LINK_input, &a, &b, &c, auts, pga, pcp);
408
409 #if defined(TIME)
410 t = runTime() - t;
411 printf("Time to compute permutations is %.2f seconds\n", t * CLK_SCALE);
412 #endif
413
414 orbit_option(STANDARDISE, perms, &a, &b, &c, &orbit_length, pga);
415 /*
416 printf ("orbit length is %d \n", orbit_length);
417 */
418
419 #if defined(GAP_LINK_VIA_FILE)
420 if (!soluble_group) {
421 CloseFile(LINK_input);
422 }
423 #endif
424
425 map = find_stabiliser(identity_map,
426 non_standard,
427 auts,
428 perms,
429 a,
430 b,
431 c,
432 orbit_length,
433 pga,
434 pcp);
435
436
437 if (pga->final_stage && output >= DEFAULT_STANDARD_PRINT) {
438 printf("\nThe standard presentation for the class %d %d-quotient is\n",
439 pcp->cc,
440 pcp->p);
441 print_presentation(TRUE, pcp);
442 #ifdef HAVE_GMP
443 s = pga->upper_bound ? "at most " : "";
444 /* Originally pq checked the whole automorphism group.
445 * Now it checks only coset reps. of inner automorphisms
446 * i.e. those auts that are in 1-1 correspondence with outer auts. */
447 printf("Subset of automorphism group to check has order bound %s", s);
448 mpz_out_str(stdout, 10, &(pga->aut_order));
449 printf("\n");
450 #endif
451 }
452
453 #if defined(GAP_LINK)
454 if (process_fork)
455 QuitGap();
456 #endif
457
458 free_space(TRUE, perms, orbit_length, a, b, c, pga);
459
460 /* memory leakage September 1996 */
461 free_vector(pga->list, 0);
462 free_vector(pga->available, 0);
463 free_vector(pga->offset, 0);
464
465 return map;
466 }
467
468 /* find the stabiliser of the representative of the orbit which
469 contains the non-standard allowable subgroup */
470
find_stabiliser(Logical * identity_map,int non_standard,int *** auts,int ** perms,int * a,int * b,char * c,int * orbit_length,struct pga_vars * pga,struct pcp_vars * pcp)471 static int **find_stabiliser(Logical *identity_map,
472 int non_standard,
473 int ***auts,
474 int **perms,
475 int *a,
476 int *b,
477 char *c,
478 int *orbit_length,
479 struct pga_vars *pga,
480 struct pcp_vars *pcp)
481 {
482 FILE *Status;
483 FILE *OutputFile;
484 Logical soluble_group;
485 int rep[2];
486 int length[2];
487 int **map;
488 int i;
489 int word_length = 0;
490 char *word_map;
491
492 #if defined(TIME)
493 int t = runTime();
494 #endif
495
496 soluble_group = (pga->soluble || pga->Degree == 1 || pga->nmr_of_perms == 0);
497
498 /* what is the orbit representative of non_standard? */
499 if (soluble_group)
500 rep[1] = abs(a[non_standard]);
501 else {
502 if (a[non_standard] < 0)
503 rep[1] = pga->rep[abs(a[non_standard])];
504 else
505 rep[1] = abs(a[non_standard]);
506 }
507
508 /* find the length of the orbit having this representative */
509 for (i = 1; i <= pga->nmr_orbits && pga->rep[i] != rep[1]; ++i)
510 ;
511 if (pga->rep[i] == rep[1]) {
512 length[1] = orbit_length[i];
513 if (output == MAX_STANDARD_PRINT)
514 printf("The non-standard subgroup %d has orbit representative %d\n",
515 non_standard,
516 pga->rep[i]);
517 } else {
518 printf("%d is not an orbit representative\n", rep[1]);
519 exit(FAILURE);
520 }
521
522 /*
523 printf ("True Orbit length is %d\n", length[1]);
524 */
525
526 word_map = find_word(&word_length,
527 soluble_group,
528 perms,
529 rep[1],
530 non_standard,
531 length[1],
532 b,
533 c,
534 pga);
535
536 /* now process this representative and find its stabiliser */
537
538 OutputFile = OpenFile("ISOM_XX", "w+");
539
540 pga->final_stage = (pga->q == pga->multiplicator_rank);
541
542 pga->nmr_of_descendants = 0;
543 pga->nmr_of_capables = 0;
544
545 pga->terminal = TRUE;
546 setup_reps(
547 rep, 1, length, perms, a, b, c, auts, OutputFile, OutputFile, pga, pcp);
548
549 /* now evaluate the action of standard map on pcp */
550 map = standard_map(
551 word_map, word_length, identity_map, rep[1], auts, pga, pcp);
552
553 #if defined(TIME)
554 t = runTime() - t;
555 printf("Time to process representative is %.2f seconds\n", t * CLK_SCALE);
556 #endif
557
558 RESET(OutputFile);
559 restore_pcp(OutputFile, pcp);
560
561 if (!pcp->complete)
562 last_class(pcp);
563
564 Status = OpenFile("ISOM_Status", "w");
565 if (pga->final_stage)
566 fprintf(Status, "%d ", END_OF_CLASS);
567 else
568 fprintf(Status, "%d ", MIDDLE_OF_CLASS);
569 if (pcp->newgen == 0)
570 fprintf(Status, "%d ", TERMINAL);
571 else
572 fprintf(Status, "%d ", CAPABLE);
573
574 CloseFile(Status);
575 CloseFile(OutputFile);
576
577 return map;
578 }
579
trace(char * word_map,int * depth,int label,int * backptr,char * schreier)580 void trace(char *word_map, int *depth, int label, int *backptr, char *schreier)
581 {
582 if (schreier[label] != 0) {
583 word_map[++*depth] = schreier[label];
584 trace(word_map, depth, backptr[label], backptr, schreier);
585 }
586 }
587
588 /* find word in defining permutations which maps orbit representative to label;
589 store each component of the word of length word_length in array word */
590
find_word(int * word_length,Logical soluble_group,int ** perms,int rep,int non_standard,int orbit_length,int * b,char * c,struct pga_vars * pga)591 static char *find_word(int *word_length,
592 Logical soluble_group,
593 int **perms,
594 int rep,
595 int non_standard,
596 int orbit_length,
597 int *b,
598 char *c,
599 struct pga_vars *pga)
600 {
601 int perm_number;
602 char *word_map;
603 char *word_perm;
604 int i, l;
605 char *d;
606 char temp;
607
608 word_map = allocate_char_vector(orbit_length, 1, FALSE);
609
610 /* we store word which maps non-standard label to orbit representative;
611 in image_of_generator, the word is evaluated starting from the
612 last letter -- hence after computing the word, we reverse it */
613
614 if (soluble_group) {
615 d = find_permutation(b, c, pga);
616 l = non_standard;
617 while (l != rep) {
618 word_map[++*word_length] = d[l];
619 if ((perm_number = pga->map[(int)d[l]]) != 0)
620 l = inverse_image(l, perms[perm_number], pga);
621 }
622 /* reverse word */
623 for (i = 1; i <= *word_length / 2; ++i) {
624 temp = word_map[i];
625 word_map[i] = word_map[*word_length - i + 1];
626 word_map[*word_length - i + 1] = temp;
627 }
628 free_char_vector(d, 1);
629 } else {
630 word_perm = allocate_char_vector(orbit_length, 1, FALSE);
631 trace(word_perm, word_length, non_standard, b, c);
632 for (i = 1; i <= *word_length; ++i)
633 word_map[i] = preimage(word_perm[*word_length - i + 1], pga);
634 free_char_vector(word_perm, 1);
635 }
636
637 return word_map;
638 }
639
640 /* compute the automorphism which maps the non-standard subgroup,
641 non_standard, to the orbit representative, rep; the word and
642 its length are supplied as word_map and word_length */
643
standard_map(char * word_map,int word_length,Logical * identity_map,int rep,int *** auts,struct pga_vars * pga,struct pcp_vars * pcp)644 static int **standard_map(char *word_map,
645 int word_length,
646 Logical *identity_map,
647 int rep,
648 int ***auts,
649 struct pga_vars *pga,
650 struct pcp_vars *pcp)
651 {
652 register int *y = y_address;
653
654 int nmr_of_generators = y[pcp->clend + pcp->cc - 1] + pga->s;
655 register int pointer = pcp->lused + 1;
656 int cp = pcp->lused;
657 int **standard;
658 int i, j;
659
660 /* copy the word into y */
661 for (i = 1; i <= word_length; ++i)
662 y[pointer + i] = word_map[i];
663 free_char_vector(word_map, 1);
664
665 y[pointer] = word_length;
666
667 #if defined(DEBUG)
668 printf("The word is ");
669 print_array(y, pointer, pointer + word_length + 1);
670 #endif
671
672 pcp->lused += word_length + 1;
673 cp = pcp->lused;
674
675 map_array_size = pcp->lastg;
676 standard = allocate_matrix(pcp->lastg, nmr_of_generators, 1, FALSE);
677
678 if (word_length == 0) {
679 for (i = 1; i <= pga->ndgen; ++i)
680 for (j = 1; j <= nmr_of_generators; ++j)
681 standard[i][j] = (i == j) ? 1 : 0;
682 *identity_map = TRUE;
683 } else {
684 for (i = 1; i <= pga->ndgen; ++i) {
685 /* compute image of defining generator i under standard map */
686 image_of_generator(i, pointer, auts, pga, pcp);
687
688 /* copy restriction of result into standard array */
689 for (j = 1; j <= nmr_of_generators; ++j) {
690 standard[i][j] = y[cp + j];
691 }
692 }
693 *identity_map = FALSE;
694 }
695 y[pointer] = 0;
696
697 if (!pga->final_stage)
698 list_subgroup(rep, pga, pcp);
699
700 return standard;
701 }
702
703 /* find the image of l under the inverse of the supplied permutation */
704
inverse_image(int l,int * perms,struct pga_vars * pga)705 static int inverse_image(int l, int *perms, struct pga_vars *pga)
706 {
707 register int i;
708
709 for (i = 1; i <= pga->Degree && perms[i] != l; ++i)
710 ;
711
712 return i;
713 }
714
715 /* write a description of the automorphism group of the
716 group presented by the standard presentation to file */
717
print_aut_description(int *** central,int *** stabiliser,struct pga_vars * pga,struct pcp_vars * pcp)718 void print_aut_description(int ***central,
719 int ***stabiliser,
720 struct pga_vars *pga,
721 struct pcp_vars *pcp)
722 {
723 FILE *NextClass;
724 int i, j, k;
725
726 NextClass = OpenFile("ISOM_NextClass", "w+");
727
728 fprintf(NextClass, "%d\n", pga->nmr_centrals + pga->nmr_stabilisers);
729 fprintf(NextClass, "%d\n", pcp->lastg);
730 for (i = 1; i <= pga->nmr_centrals; ++i) {
731 for (j = 1; j <= pga->ndgen; ++j) {
732 for (k = 1; k <= pcp->lastg; ++k)
733 fprintf(NextClass, "%d ", central[i][j][k]);
734 fprintf(NextClass, "\n");
735 }
736 }
737
738 for (i = 1; i <= pga->nmr_stabilisers; ++i)
739 for (j = 1; j <= pga->ndgen; ++j) {
740 for (k = 1; k <= pcp->lastg; ++k)
741 fprintf(NextClass, "%d ", stabiliser[i][j][k]);
742 fprintf(NextClass, "\n");
743 }
744
745 fprintf(NextClass, "%d\n", pga->fixed);
746 fprintf(NextClass, "%d\n", pga->soluble);
747
748 #ifdef HAVE_GMP
749 mpz_out_str(NextClass, 10, &pga->aut_order);
750 fprintf(NextClass, "\n");
751 #endif
752
753 CloseFile(NextClass);
754 }
755
756 /* list orbit representative as generators of subgroup to
757 factor from p-covering group */
758
list_subgroup(int rep,struct pga_vars * pga,struct pcp_vars * pcp)759 static void list_subgroup(int rep, struct pga_vars *pga, struct pcp_vars *pcp)
760 {
761 register int lastg = pcp->lastg;
762 register int i, j, k;
763 FILE *Subgroup;
764 int word[MAXWORD];
765 int *subset;
766 int **S;
767 int index;
768 int length = 0;
769
770 if (pga->s == pga->q)
771 return;
772
773 Subgroup = OpenFile("ISOM_Subgroup", "a+");
774 S = label_to_subgroup(&index, &subset, rep, pga);
775
776 #if defined(DEBUG)
777 printf("The standard matrix is\n");
778 print_matrix(S, pga->s, pga->q);
779 #endif
780
781 for (i = 0; i < pga->q; ++i) {
782
783 if (1 << i & pga->list[index])
784 continue;
785
786 for (j = 1; j <= lastg; ++j)
787 word[j] = 0;
788
789 for (j = 0; j < pga->s; ++j)
790 if (S[j][i] != 0)
791 word[pcp->ccbeg + subset[j]] = pga->p - S[j][i];
792
793 word[pcp->ccbeg + i] = 1;
794
795 #if defined(DEBUG)
796 printf("The subgroup generator is ");
797 print_array(word, pcp->ccbeg, pcp->ccbeg + pga->q);
798 #endif
799
800 length = 0;
801 for (k = pcp->ccbeg; k <= lastg; ++k)
802 if (word[k] != 0)
803 ++length;
804
805 fprintf(Subgroup, "%d\n", COLLECT);
806 for (k = pcp->ccbeg; k <= lastg; ++k) {
807 if (word[k] != 0) {
808 fprintf(Subgroup, "x%d^%d", k, word[k]);
809 if (--length != 0)
810 fprintf(Subgroup, " * ");
811 }
812 }
813 fprintf(Subgroup, ";\n");
814 }
815
816 /* memory leakage September 1996 */
817 free_matrix(S, pga->s, 0);
818 free_vector(subset, 0);
819
820 /* write out flag to indicate that we should now eliminate
821 redundant generators */
822 fprintf(Subgroup, "%d\n", ELIMINATE);
823
824 CloseFile(Subgroup);
825 }
826
827 /* for each automorphism in turn, read its actions on each
828 of the pcp generators of the Frattini quotient */
829
read_auts_from_file(FILE * file,int * nmr_of_auts,struct pcp_vars * pcp)830 int ***read_auts_from_file(FILE *file, int *nmr_of_auts, struct pcp_vars *pcp)
831 {
832 register int *y = y_address;
833
834 register int i, j, k;
835 int ***auts;
836 int nmr_of_exponents, nmr_of_generators;
837 int nmr_items;
838
839 nmr_items = fscanf(file, "%d", nmr_of_auts);
840 verify_read(nmr_items, 1);
841
842 nmr_items = fscanf(file, "%d", &nmr_of_exponents);
843 verify_read(nmr_items, 1);
844
845 nmr_of_generators = y[pcp->clend + 1];
846
847 auts = allocate_array(*nmr_of_auts, pcp->lastg, pcp->lastg, TRUE);
848
849 for (i = 1; i <= *nmr_of_auts; ++i) {
850 for (j = 1; j <= nmr_of_generators; ++j) {
851 for (k = 1; k <= nmr_of_exponents; ++k)
852 nmr_items = fscanf(file, "%d", &auts[i][j][k]);
853 verify_read(nmr_items, 1);
854 }
855 }
856
857 return auts;
858 }
859
860 #endif
861