1 /****************************************************************************
2 **
3 ** engel.c NQ Werner Nickel
4 ** nickel@mathematik.tu-darmstadt.de
5 */
6
7
8 #include "nq.h"
9 #include "engel.h"
10 #include "presentation.h"
11 #include "glimt.h"
12
13 static int LeftEngel = 0, RightEngel = 0, Engel = 0;
14 static int RevEngel = 0;
15 static int NrEngelGens = 0;
16 static int NrWords;
17 static int Needed;
18 static word A;
19 int SemigroupOnly = 0;
20 int SemigroupFirst = 0;
21 int CheckFewInstances = 0;
22 int ReverseOrder = 0;
23
24 static
Error(word v,word w,char type)25 void Error(word v, word w, char type) {
26 printf("Overflow in collector computing [ ");
27 printWord(v, 'a');
28 if (type == 'e') printf(" , %d ", Engel);
29 if (type == 'l') printf(" , %d ", LeftEngel);
30 if (type == 'r') printf(" , %d ", RightEngel);
31 printWord(w, 'a');
32 printf(" ]\n");
33 }
34
35
EngelCommutator(word v,word w,int engel)36 word EngelCommutator(word v, word w, int engel) {
37 long n;
38 word v1;
39
40
41 if (Class + 1 < engel) {
42 v1 = (word)Allocate(sizeof(gpower));
43 v1[0].g = EOW;
44 v1[0].e = (expo)0;
45 return v1;
46 }
47
48 /*
49 ** If the current class reaches the weight of the engel condition,
50 ** then we want to speed up the evaluation of the engel relations by
51 ** evaluating each commutator only with the required precision. The
52 ** last commutator of an Engel-n commutator has to be evaluated in
53 ** class (Class+1) quotient (i.e. the full group), the second last in
54 ** the class Class quotient, etc. The first commutator has to be
55 ** evaluated in the class (Class+1-(n-1)) quotient. See also the
56 ** function SetupCommuteList() in addgen.c
57 */
58
59 n = 1;
60 Class = Class - (engel - 1);
61
62 if ((v = Commutator(v, w)) == (word)0)
63 return (word)0;
64
65 n++;
66 while (n <= engel) {
67 Class++;
68
69 if ((v1 = Commutator(v, w)) == (word)0)
70 return (word)0;
71
72 Free(v);
73 v = v1;
74
75 n++;
76 }
77 return v;
78 }
79
80 static
evalEngelRel(word v,word w)81 void evalEngelRel(word v, word w) {
82 word comm;
83 long needed;
84
85 /* printf( "evalEngelRel() called with : " );
86 printWord( v, 'A' ); printf( " " );
87 printWord( w, 'A' ); putchar( '\n' ); */
88
89 NrWords++;
90
91 /* Calculate [ v, w, .., w ] */
92 if ((comm = EngelCommutator(v, w, Engel)) == (word)0) {
93 Error(v, w, 'e');
94 return;
95 }
96
97 needed = addRow(ExpVecWord(comm));
98 if (needed) {
99 printf("# [ ");
100 printWord(v, 'a');
101 printf(", %d ", Engel);
102 printWord(w, 'a');
103 printf(" ]\n");
104 }
105 if (CheckFewInstances) Needed |= needed;
106 else Needed = 1;
107
108 Free(comm);
109 }
110
111 static
buildPairs(word u,long i,gen g,word v,long wt,long which)112 void buildPairs(word u, long i, gen g, word v, long wt, long which) {
113 long save_wt;
114
115
116 /* First we check if the Engel condition is trivially
117 satisfied for weight reasons. The commutator
118 [u, n v] is 1 if w(u) + n*w(v) > Class+1. */
119 if (which == 1 && i == 1 &&
120 Wt(abs(u[0].g)) + Engel * Wt(abs(v[0].g)) > Class + 1)
121 return;
122
123 if (wt == 0 && which == 1 && i > 0) {
124 evalEngelRel(u, v);
125 return;
126 }
127
128 /* Keep u and start to build v. */
129 if (i > 0 && which == 2) buildPairs(v, 0, 1, u, wt, 1);
130
131 if (g > NrPcGens) return;
132
133 save_wt = wt;
134 while (!EarlyStop &&
135 g <= NrPcGens && Wt(g) <= Class + 1 - Engel && Wt(g) <= wt) {
136 u[i].g = g;
137 u[i].e = (expo)0;
138 u[i + 1].g = EOW;
139 while (!EarlyStop && Wt(g) <= wt) {
140 u[i].e++;
141 if (Exponent[g] > (expo)0 && Exponent[g] == u[i].e) break;
142 wt -= Wt(g);
143 buildPairs(u, i + 1, g + 1, v, wt, which);
144 /* now build the same word with negative exponent */
145 if (!EarlyStop && !SemigroupOnly && Exponent[g] == (expo)0) {
146 u[i].g *= -1;
147 buildPairs(u, i + 1, g + 1, v, wt, which);
148 u[i].g *= -1;
149 }
150 }
151 wt = save_wt;
152 g++;
153 }
154 u[i].g = EOW;
155 u[i].e = (expo)0;
156 if (EarlyStop || SemigroupOnly || !SemigroupFirst) return;
157
158 while (!EarlyStop &&
159 g <= NrPcGens && Wt(g) <= Class + 1 - Engel && Wt(g) <= wt) {
160 u[i].g = -g;
161 u[i].e = (expo)0;
162 u[i + 1].g = EOW;
163 while (!EarlyStop && Wt(g) <= wt) {
164 u[i].e++;
165 if (Exponent[g] > (expo)0 && Exponent[g] == u[i].e) break;
166 wt -= Wt(g);
167 buildPairs(u, i + 1, g + 1, v, wt, which);
168 if (EarlyStop) return;
169 /* now build the same word with negative exponent */
170 if (!EarlyStop && !SemigroupOnly && Exponent[g] == (expo)0) {
171 u[i].g *= -1;
172 buildPairs(u, i + 1, g + 1, v, wt, which);
173 u[i].g *= -1;
174 }
175 }
176 wt = save_wt;
177 g++;
178 }
179 u[i].g = EOW;
180 u[i].e = (expo)0;
181 }
182
183 static
evalEngel(void)184 void evalEngel(void) {
185 word u, v;
186 long c;
187
188 u = (word)Allocate((NrPcGens + NrCenGens + 1) * sizeof(gpower));
189 v = (word)Allocate((NrPcGens + NrCenGens + 1) * sizeof(gpower));
190
191 /* For `production purposes' I don't want to run through */
192 /* those classes that don't yield non-trivial instances of the */
193 /* Engel law. Therefore, we stop as soon as we ran through a */
194 /* class that didn't yield any non-trivial instances. This is */
195 /* done through the static variable Needed which is set by */
196 /* evalEngelRel() as soon as a non-trivial instance has been */
197 /* found if the flag CheckFewInstances (option -c) is set. */
198 if (ReverseOrder)
199 for (c = Class + 1; !EarlyStop && c >= 2; c--) {
200 u[0].g = EOW;
201 u[0].e = (expo)0;
202 v[0].g = EOW;
203 v[0].e = (expo)0;
204 NrWords = 0;
205 if (Verbose)
206 printf("# Checking pairs of words of weight %ld\n", c);
207 buildPairs(u, 0, 1, v, c, 2);
208 if (Verbose) printf("# Checked %d words.\n", NrWords);
209 }
210 else {
211 Needed = 1;
212 for (c = 2; !EarlyStop && Needed && c <= Class + 1; c++) {
213 Needed = 0;
214 u[0].g = EOW;
215 u[0].e = (expo)0;
216 v[0].g = EOW;
217 v[0].e = (expo)0;
218 NrWords = 0;
219 if (Verbose)
220 printf("# Checking pairs of words of weight %ld\n", c);
221 buildPairs(u, 0, 1, v, c, 2);
222 if (Verbose) printf("# Checked %d words.\n", NrWords);
223 }
224 for (; !EarlyStop && c <= Class + 1; c++)
225 printf("# NOT checking pairs of words of weight %ld\n", c);
226 }
227 free(u);
228 free(v);
229 }
230
231 static
evalRightEngelRel(word w)232 void evalRightEngelRel(word w) {
233 word comm;
234 long n, needed;
235
236 /* printf( "evalRightEngelRel() called with : " );*/
237 /* printWord( w, 'A' );*/
238 /* putchar( '\n' );*/
239
240 NrWords++;
241 /* Calculate [ a, w, .., w ] */
242 if ((comm = EngelCommutator(A, w, RightEngel)) == (word)0) {
243 Error(A, w, 'r');
244 return;
245 }
246
247 needed = addRow(ExpVecWord(comm));
248 if (needed) {
249 printf("# [ ");
250 printWord(A, 'a');
251 for (n = RightEngel - 1; n >= 0; n--) {
252 printf(", ");
253 printWord(w, 'a');
254 }
255 printf(" ]\n");
256 }
257 if (CheckFewInstances) Needed |= needed;
258 else Needed = 1;
259
260 Free(comm);
261 }
262
263 static
evalLeftEngelRel(word w)264 void evalLeftEngelRel(word w) {
265 word comm;
266 long n, needed;
267
268 /* printf( "evalLeftEngelRel() called with : " );*/
269 /* printWord( w, 'A' );*/
270 /* putchar( '\n' );*/
271
272 NrWords++;
273 /* Calculate [ w, a, .., a ] */
274
275 if ((comm = EngelCommutator(w, A, LeftEngel)) == (word)0) {
276 Error(w, A, 'l');
277 return;
278 }
279
280 needed = addRow(ExpVecWord(comm));
281 if (needed) {
282 printf("# [ ");
283 printWord(w, 'a');
284 for (n = LeftEngel - 1; n >= 0; n--) {
285 printf(", ");
286 printWord(A, 'a');
287 }
288 printf(" ]\n");
289 }
290 if (CheckFewInstances) Needed |= needed;
291 else Needed = 1;
292
293 Free(comm);
294 }
295
296 static
buildWord(word u,long i,gen g,long wt)297 void buildWord(word u, long i, gen g, long wt) {
298 long save_wt;
299
300 if (wt == 0 && i > 0) {
301 if (RightEngel) evalRightEngelRel(u);
302 if (LeftEngel) evalLeftEngelRel(u);
303 return;
304 }
305
306 if (g > NrPcGens) return;
307
308 save_wt = wt;
309 while (!EarlyStop && g <= NrPcGens && Wt(g) <= wt) {
310 u[i].g = g;
311 u[i].e = (expo)0;
312 u[i + 1].g = EOW;
313 while (!EarlyStop && Wt(g) <= wt) {
314 u[i].e++;
315 if (Exponent[g] > (expo)0 && Exponent[g] == u[i].e) break;
316 wt -= Wt(g);
317 buildWord(u, i + 1, g + 1, wt);
318 /* now build the same word with negative exponent */
319 if (!EarlyStop && !SemigroupOnly &&
320 !SemigroupFirst && Exponent[g] == (expo)0) {
321 u[i].g *= -1;
322 buildWord(u, i + 1, g + 1, wt);
323 u[i].g *= -1;
324 }
325 }
326 wt = save_wt;
327 g++;
328 }
329 u[i].g = EOW;
330 u[i].e = (expo)0;
331 if (EarlyStop || SemigroupOnly || !SemigroupFirst) return;
332 while (!EarlyStop && g <= NrPcGens && Wt(g) <= wt) {
333 u[i].g = -g;
334 u[i].e = (expo)0;
335 u[i + 1].g = EOW;
336 while (!EarlyStop && Wt(g) <= wt) {
337 u[i].e++;
338 if (Exponent[g] > (expo)0 && Exponent[g] == u[i].e) break;
339 wt -= Wt(g);
340 buildWord(u, i + 1, g + 1, wt);
341 }
342 wt = save_wt;
343 g++;
344 }
345 u[i].g = EOW;
346 u[i].e = (expo)0;
347 }
348
349 static
evalLREngel(void)350 void evalLREngel(void) {
351
352 word u;
353 int n;
354 long cl;
355
356 A = (word)Allocate(2 * sizeof(gpower));
357 u = (word)Allocate((NrPcGens + NrCenGens + 1) * sizeof(gpower));
358
359 for (n = 1; !EarlyStop && n <= NrEngelGens; n++) {
360
361 if (RevEngel) A[0].g = NumberOfAbstractGens() - n + 1;
362 else A[0].g = n;
363 A[0].e = (expo)1;
364 A[1].g = EOW;
365 A[1].e = (expo)0;
366
367 Needed = 1;
368 for (cl = 2; !EarlyStop && Needed && cl <= Class + 1; cl++) {
369 Needed = 0;
370 u[0].g = EOW;
371 u[0].e = (expo)0;
372 NrWords = 0;
373 if (Verbose) printf("# Checking words of weight %ld\n", cl - 1);
374 buildWord(u, 0, 1, cl - 1);
375 if (Verbose) printf("# Checked %d words.\n", NrWords);
376 }
377 for (; !EarlyStop && cl <= Class + 1; cl++)
378 printf("# NOT checking words of weight %ld\n", cl);
379
380 }
381 free(u);
382 free(A);
383 }
384
EvalEngel(void)385 void EvalEngel(void) {
386
387 long t = 0;
388
389 if (Verbose) t = RunTime();
390
391 if (LeftEngel || RightEngel) evalLREngel();
392 if (Engel) evalEngel();
393
394 if (Verbose)
395 printf("# Evaluated Engel condition (%ld msec).\n", RunTime() - t);
396 }
397
InitEngel(int l,int r,int v,int e,int n)398 void InitEngel(int l, int r, int v, int e, int n) {
399 LeftEngel = l;
400 RightEngel = r;
401 RevEngel = v;
402
403 Engel = e;
404
405 NrEngelGens = n;
406 }
407