1#/***************************************************************/
2#/*   Recognise quasi-simple group of Lie type when             */
3#/*   characteristic is given                                   */
4#/*                                                             */
5#/*   Babai, Kantor, Palfy, Seress:
6#/*   "Black-box recognition of finite simple groups of Lie type
7#/*   by statistics of element orders", Journal of Group Theory
8#/*   5.4 (2002): 383-402.
9#/*   Altseimer & Borovik (2001)                                */
10#/*   provide theoretical basis for algorithms                  */
11#/*                                                             */
12#/*   this version developed by Malle & O'Brien March 2001      */
13#/*                                                             */
14#/***************************************************************/
15#
16
17# GAP translation attempt Jan 2004 SL
18
19RECOG.LieTypeOrderFunc := RECOG.ProjectiveOrder;
20RECOG.LieTypeSampleSize := 250;
21RECOG.LieTypeNmrTrials := 10;
22
23RECOG.OMppdset := function(p, o)
24    local   primes;
25    primes := Set(Factors(o));
26    RemoveSet(primes,p);
27    return Set(primes, l->OrderMod(p,l));
28end;
29
30RECOG.VerifyOrders := function (type, n, q, orders)
31    local   p,  allowed,  maxprime,  r,  rq,  ii, LargestPrimeOccurs;
32    LargestPrimeOccurs := function(r, orders)
33        local   maxp;
34        maxp := Maximum(Factors(r));
35        return ForAny(orders, i->i mod maxp = 0);
36    end;
37    p := Factors(q)[1];
38    allowed := orders;
39    maxprime := true;
40    if type = "L" then
41        if n = 2 then
42            if p = 2 then
43                allowed := Set([2, q-1, q+1]);
44            else
45                allowed := Set([p, (q-1)/2, (q+1)/2]);
46          fi;
47      elif n = 3 then
48          if (q-1) mod 3 <> 0 then
49              allowed := Set([4, p* (q-1), q^2-1, q^2+q+1]);
50          else
51              allowed := Set([4, p* (q-1)/3, q-1, (q^2-1)/3, (q^2+q+1)/3]);
52          fi;
53      elif n = 4 then
54          if p = 2 then
55              allowed := Set([4* (q-1), p* (q^2-1), q^3-1, (q^2+1)* (q-1),
56                              (q^2+1)* (q+1)]);
57          elif p = 3 then
58              allowed := Set([9, p* (q^2-1), q^3-1, (q^2+1)* (q-1),
59                              (q^2+1)* (q+1)]);
60          elif (q-1) mod 2 <> 0 then
61              allowed := Set([p*(q^2-1),q^3-1,(q^2+1)* (q-1), (q^2+1)* (q+1)]);
62          elif (q-1) mod 4 = 2 then
63              allowed := Set([p* (q^2-1), (q^3-1)/2, (q^2+1)* (q-1)/2,
64                              (q^2+1)* (q+1)/2 ]);
65          else
66              allowed := Set([p* (q^2-1), (q^3-1)/4, (q^2+1)* (q-1)/4,
67                              (q^2+1)* (q+1)/4 ]);
68          fi;
69      elif n = 5 and q = 2 then
70          allowed := Set([8, 12, 14, 15, 21, 31]);
71      elif n = 6 and q = 3 then
72          allowed := Set([36, 78, 80, 104, 120, 121, 182]);
73          maxprime := 91 in orders or 121 in orders;
74      else
75          maxprime := LargestPrimeOccurs (q^n-1, orders)
76                      and LargestPrimeOccurs (q^(n-1)-1, orders)
77                      and Maximum (orders) <= (q^n-1)/ (q-1)/Gcd (n,q-1);
78          if n = 8 and q = 2 then
79              maxprime := maxprime and LargestPrimeOccurs (7, orders);
80              #/Set([ i : i in orders | i mod 21 = 0]) <> Set([]);
81          fi;
82      fi;
83  elif type = "U" then
84      if n = 3 then
85          if (q+1) mod 3 <> 0 then
86              allowed := Set([4, p* (q+1), q^2-1, q^2-q+1]);
87          else
88              allowed := Set([4, p* (q+1)/3, q+1, (q^2-1)/3, (q^2-q+1)/3]);
89          fi;
90      elif n = 4 then
91          if p = 2 then
92              allowed := Set([8, 4* (q+1), p* (q^2-1), q^3+1, (q^2+1)* (q-1),
93                              (q^2+1)* (q+1)]);
94          elif p = 3 then
95              allowed := Set([9, p* (q^2-1), q^3+1, (q^2+1)* (q-1),
96                              (q^2+1)* (q+1)]);
97              if q = 3 then
98                  maxprime := 8 in orders and 9 in orders;
99              fi;
100          elif (q+1) mod 2 <> 0 then
101              allowed := Set([p*(q^2-1),q^3+1,(q^2+1)* (q-1), (q^2+1)* (q+1)]);
102          elif (q+1) mod 4 = 2 then
103              allowed := Set([p* (q^2-1), (q^3+1)/2, (q^2+1)* (q-1)/2,
104                              (q^2+1)* (q+1)/2 ]);
105              if q = 5 then
106                  maxprime := Maximum (orders) > 21;
107              fi;
108          else
109              allowed := Set([p* (q^2-1), (q^3+1)/4, (q^2+1)* (q-1)/4,
110                              (q^2+1)* (q+1)/4 ]);
111          fi;
112      else
113          r := 2 * ((n-1)/2)+1;
114          maxprime := LargestPrimeOccurs (q^r+1, orders)
115                      and Maximum (orders) <= (q^(r+1)-1)/ (q-1);
116          if n = 6 and q = 2 then
117              maxprime := maxprime and 18 in orders;
118          fi;
119      fi;
120  elif type = "S" then
121      if n = 4 then
122          if q mod 2 = 0 then
123              allowed := Set([4, p * (q-1), p * (q+1), q^2-1, q^2+1]);
124          elif q mod 3 = 0 then
125              allowed := Set([9, p * (q-1), p * (q+1), (q^2-1)/2, (q^2+1)/2]);
126          else
127              allowed := Set([p * (q-1), p * (q+1), (q^2-1)/2, (q^2+1)/2]);
128          fi;
129      elif n = 6 and q = 2 then
130          allowed := Set([ 7, 8, 9, 10, 12, 15 ]);
131          maxprime := 8 in orders and 15 in orders;
132      else
133          maxprime := LargestPrimeOccurs (q^(n/2)+1, orders) and
134                      LargestPrimeOccurs (q^(n/2)-1, orders);
135      fi;
136  elif type = "O^+" and n = 8 and q = 2 then
137      allowed := Set([ 7, 8, 9, 10, 12, 15 ]);
138      maxprime := 8 in orders and 15 in orders;
139  elif type = "O^+" and n = 10 and q = 2 then
140      allowed := Set([ 18, 24, 31, 42, 45, 51, 60]);
141  elif type = "O^-" then
142      maxprime := LargestPrimeOccurs (q^(n/2)+1, orders) and
143                  LargestPrimeOccurs (q^(n/2 -1)-1, orders);
144  elif type = "2B" then
145      rq := RootInt(2*q);
146      allowed := Set([4, q-1, q-rq+1, q+rq+1]);
147  elif type = "2G" then
148      rq := RootInt(3*q);
149      allowed := Set([9, 3* (q-1), q+1, q-rq+1, q+rq+1]);
150  elif type = "G" then
151      if p = 2 then
152          allowed := Set([8, 4 * (q-1), 4 * (q+1), q^2-1, q^2-q+1, q^2+q+1]);
153      elif p <= 5 then
154          allowed := Set([p^2, p * (q-1), p * (q+1), q^2-1, q^2-q+1, q^2+q+1]);
155      else
156          allowed := Set([p * (q-1), p * (q+1), q^2-1, q^2-q+1, q^2+q+1]);
157      fi;
158  elif type = "2F" and q = 2 then
159      allowed := Set([10, 12, 13, 16 ]);
160  elif type = "2F" and q = 8 then
161      allowed := Set([ 12, 16, 18, 20, 28, 35, 37, 52, 57, 63, 65, 91, 109 ]);
162      maxprime := Maximum (orders) > 37;
163  elif type = "3D" and q = 2 then
164      allowed := Set([ 8, 12, 13, 18, 21, 28 ]);
165      maxprime := Maximum (orders) > 13;
166  elif type = "F" and q = 2 then
167      allowed := Set([ 13, 16, 17, 18, 20, 21, 24, 28, 30 ]);
168  elif type = "2E" and q = 2 then
169      allowed := Set([ 13, 16, 17, 18, 19, 20, 21, 22, 24, 28, 30, 33, 35 ]);
170  elif type = "E" and n = 7 and q = 2 then
171      maxprime := Maximum (orders) <= 255;
172  fi;
173
174  if not maxprime then
175      return "RO_CONTRADICTION";
176  fi;
177  for ii in allowed do
178      orders := Filtered( orders, o-> ii mod o <> 0 );
179  od;
180  if orders = [] then
181      return Concatenation(type,String(n), "(", String(q), ")");
182  else
183      return  "RO_CONTRADICTION";
184  fi;
185end;  #  VerifyOrders
186
187#/*  P random process for group;
188#    distinguish PSp (2n, p^e) from Omega (2n + 1, p^e);
189#    orders are orders of elements */
190#
191
192RECOG.DistinguishSpO := function (G, n, p, e, orders)
193    local   twopart,   q,  goodtorus,  t1,  tp,  t2,
194            found,  tf,  ttf,  g,  o,  mp,  i,  x,  z,  po,  h;
195
196    twopart := function (n)
197        local k;
198        k := 1;
199        while n mod 2 = 0 do
200            n := n/2;
201            k := k*2;
202        od;
203        return k;
204    end;
205
206    q := p^e;
207    if n mod 2 = 1 and (q + 1) mod 4 = 0 then
208        goodtorus := 2 * n;
209        t1 := q^n + 1;
210        tp := twopart ((q^n + 1) / 2);
211    else
212        goodtorus := n;
213        t1 := q^n - 1;
214        tp := twopart ((q^n - 1) / 2);
215    fi;
216    t2 := q^QuoInt(n , 2) + 1;
217
218    found := false;
219    tf := 0; ttf := 0;  # counters to deal with wrong char groups
220    repeat
221        g := PseudoRandom (G);
222        o := RECOG.LieTypeOrderFunc (g);
223        if o mod p <> 0 then
224            ttf := ttf+1;
225            mp := RECOG.OMppdset (p, o);
226
227
228            if 2*o = t1 then
229                tf := tf+1;
230                g := g^(o / 2);
231                found := n mod 2 = 1;
232                i := 0;
233                while not found and i < 8 * n do
234                    i := i+1;
235                    x := PseudoRandom (G);
236                    z := g * g^x;
237                    o := RECOG.LieTypeOrderFunc (z);
238                    if o mod 2 = 1 then
239                        po := RECOG.LieTypeOrderFunc (z^((o + 1) / 2) / x);
240                        mp := RECOG.OMppdset (p, po);
241                        if (q - 1) mod 4 = 0 and (n - 1) * e in mp or
242                           (q + 1) mod 4 = 0 and 2 * (n - 1) * e in mp or
243                           (q - 1) mod 4 = 0 and 2 * (n - 1) * e in mp or
244                           (q + 1) mod 4 = 0 and 2 * n * e in mp
245#                              or (n = 4 and 6 in mp)
246                           then
247                            found := true;
248                  #printf"mp= %o, o (z)= %o\n", mp, Factorization (oo);
249                        fi;
250                    fi;
251                od;
252            fi;
253        fi;
254    until found or (tf > 15) or (ttf > 80);
255    if ttf > 80 then
256        return "RO_NO_LUCK";
257    fi;
258
259    for i in [1..6 * n] do
260        h := PseudoRandom (G);
261        o := Order (g * g^h);
262        if (q * (q + 1) mod o <> 0) and (q * (q - 1) mod o <> 0)
263           then
264            return RECOG.VerifyOrders ("S", 2 * n, q, orders);
265        fi;
266    od;
267
268    return RECOG.VerifyOrders ("O", 2 * n + 1, q, orders);
269
270end;   # DistinguishSpO
271
272#
273#/* compute Artin invariants for element of order o;
274#   p is characteristic */
275
276RECOG.ComputeArtin := function (o, p)
277    local   IsFermat,  IsMersenne,  primes,  orders;
278    IsFermat := n-> IsPrime(n) and Set(Factors(n-1)) = [2];
279    IsMersenne := n->IsPrime(n) and Set(Factors(n+1)) = [2];
280    primes := Set(Factors(o));
281    RemoveSet(primes,p);
282    RemoveSet(primes,2);
283    orders := Set(primes, x-> OrderMod(p, x));
284
285    if IsFermat (p) and o mod 4 = 0 then
286        AddSet(orders,1);
287    fi;
288    if IsMersenne (p) and o mod 4 = 0 then
289        AddSet(orders,2);
290    fi;
291    if p = 2 and o mod 9 = 0 then
292        AddSet(orders, 6);
293    fi;
294    return orders;
295end;
296
297#/* partition at most Nmr elements according to their
298#   projective orders listed in values; we consider
299#   at most NmrTries elements; P is a random process */
300
301RECOG.ppdSample := function (G, ppd, p, values, SampleSize)
302    local   Bins,  x,  j,  original,  NmrTries,  g,  o,  list;
303
304    Bins := ListWithIdenticalEntries(Length(values),0);
305
306   for x in ppd do
307       for j in [1..Length(values)] do
308           if values[j] in x then
309               Bins[j] := Bins[j] + 1;
310           fi;
311       od;
312   od;
313   original := Length(ppd);
314
315   ppd := [];
316
317   NmrTries := 0;
318   while NmrTries <= SampleSize do
319       NmrTries := NmrTries + 1;
320       g := PseudoRandom (G);
321       o := Order (g);
322       list := RECOG.ComputeArtin (o, p);
323       Add (ppd, list);
324       for j in [1..Length(values)] do
325           if values[j] in list then
326               Bins[j] := Bins[j]+1;
327           fi;
328       od;
329   od;
330
331
332   return [Bins/(original + SampleSize), ppd, Bins];
333
334end;
335
336RECOG.OrderSample := function (G, p, orders, values, SampleSize)
337    local    Bins,  i,  j,  original,  NmrTries,  g,  o,
338            Total;
339
340    Bins := ListWithIdenticalEntries(Length(values),0);
341
342   for i in orders do
343      for j in [1..Length(values)] do
344         if i mod values[j] = 0 then
345            Bins[j] := Bins[j] + 1;
346         fi;
347      od;
348   od;
349   original := Length(orders);
350
351   NmrTries := 0;
352   while NmrTries <= SampleSize do
353      NmrTries := NmrTries + 1;
354      g := PseudoRandom (G);
355      o := RECOG.LieTypeOrderFunc (g);
356      Add (orders, o);
357      for j in [1..Length(values)] do
358         if o mod values[j] = 0 then
359            Bins[j] := Bins[j]+1;
360         fi;
361      od;
362      Total := Sum(Bins);
363   od;
364
365   return [ Bins/ (SampleSize + original), orders, Bins] ;
366
367end;
368
369# PSL (2, p^k) vs PSp (4, p^(k / 2))
370RECOG.PSLvsPSP := function (G, ppd, q, SampleSize, NmrTrials, orders)
371    local   p,  g,  o,  v1,  values,  temp,  prob;
372   p := Factors (q)[1];
373   if q = 2 then
374      repeat
375         SampleSize := SampleSize - 1;
376         g := PseudoRandom (G);
377         o := RECOG.LieTypeOrderFunc (g);
378         if o = 4 then
379            return RECOG.VerifyOrders ("L",2,9, orders);
380         fi;
381      until SampleSize = 0;
382      return RECOG.VerifyOrders ("L",2,4, orders);
383   fi;
384
385   v1 := Maximum (ppd);
386   ppd := [];
387   values := [v1];
388   repeat
389       temp := RECOG.ppdSample (G, ppd, p, values, SampleSize);
390       prob := temp[1];
391       ppd  := temp[2];
392       prob := prob[1];
393       if prob >= 1/3 and prob < 1/2 then
394           return RECOG.VerifyOrders ("L",2, q^2, orders);
395       elif prob >= 1/5 and prob < 1/4 then
396           return RECOG.VerifyOrders ("S",4, q, orders);
397       fi;
398       NmrTrials := NmrTrials + 1;
399   until NmrTrials = 0;
400
401   if NmrTrials = 0 then
402#      return "Have not settled this recognition";
403      return "RO_NO_LUCK";
404   fi;
405
406end;
407
408
409RECOG.OPlus82vsS62 := function (G, orders, SampleSize)
410    local   values,  temp,  prob;
411    values := [15];
412    temp := RECOG.OrderSample (G, 2, [], values, SampleSize);
413    prob := temp[1];
414    orders := temp[2];
415    prob := prob[1];
416#"prob is ", prob;
417    if AbsoluteValue (1/5 - prob) < AbsoluteValue (1/15 - prob) then
418        return RECOG.VerifyOrders ("O^+",8, 2, orders );
419    else
420        return RECOG.VerifyOrders ("S",6, 2, orders );
421    fi;
422end;
423
424RECOG.OPlus83vsO73vsSP63 := function (G, orders, SampleSize)
425    local   values,  temp,  prob;
426    values := [20];
427    temp := RECOG.OrderSample (G, 3, [], values, SampleSize);
428    prob := temp[1];
429    orders := temp[2];
430    prob := prob[1];
431    if AbsoluteValue (3/20 - prob) < AbsoluteValue (1/20 - prob) then
432        return "O^+_8(3)";
433    else
434        return RECOG.DistinguishSpO (G, 3, 3, 1, orders);
435    fi;
436end;
437
438
439RECOG.OPlus8vsO7vsSP6 := function (G, orders, p, e, SampleSize)
440    local   i,  g,  o,  list;
441
442   for i in [1..SampleSize] do
443       g := PseudoRandom (G);
444       o := RECOG.LieTypeOrderFunc (g);
445       list := RECOG.ComputeArtin (o, p);
446       if IsSubset(list, [e, 2 * e, 4 * e]) then
447           return RECOG.VerifyOrders ("O^+",8, p^e , orders);
448       fi;
449   od;
450   if p = 2 then
451       return RECOG.VerifyOrders ("S",6, 2^e, orders);
452   else
453       return RECOG.DistinguishSpO (G, 3, p, e, orders);
454   fi;
455end;
456
457
458#// O- (8, p^e) vs S (8, p^e) vs O (9, p^e)
459RECOG.OMinus8vsSPvsO := function (G, v1, p, e, orders, SampleSize, NmrTrials)
460    local   ppd,  values,  epsilon,  temp,  prob;
461    ppd := [];
462    values := [v1];
463    epsilon := 1/50;
464    repeat
465        temp := RECOG.ppdSample (G, ppd, p, values, SampleSize);
466        prob := temp[1];
467        ppd := temp[2];
468#"prob is ", prob;
469        prob := prob[1];
470        if prob >= 1/5 - epsilon and prob < 1/4 + epsilon then
471            return RECOG.VerifyOrders ("O^-",8, p^(v1/8), orders);
472        elif prob >= 1/10 - epsilon and prob < 1/8 + epsilon then
473            if p = 2 then
474                return RECOG.VerifyOrders ("S",8, 2^e, orders);
475            else
476                return RECOG.DistinguishSpO (G, 4, p, e, orders);
477            fi;
478        fi;
479        NmrTrials := NmrTrials - 1;
480    until NmrTrials = 0;
481
482    if NmrTrials = 0 then
483#      return "Have not settled this recognition";
484        return "RO_NO_LUCK";
485    fi;
486
487end;
488
489RECOG.ArtinInvariants := function (G, p, Nmr)
490    local   orders,  combs,  invariants,  newv1,  v1,  i,  g,  o,
491            ppds;
492
493    orders := [];
494    combs := [];
495    if p > 2 then
496        invariants := [0, 1, 2];
497    else
498        invariants := [0, 1];
499    fi;
500    newv1 := Maximum (invariants);
501    repeat
502        v1 := newv1;
503        for i in [1..Nmr] do
504            g := PseudoRandom (G);
505            o := RECOG.LieTypeOrderFunc (g);
506            AddSet (orders, o);
507            if o mod 3 = 0 then
508                AddSet(orders,3);
509            fi;
510            if o mod 4 = 0 then
511                AddSet (orders, 4);
512            fi;
513            ppds := RECOG.OMppdset (p, o);
514            if p = 2 and o mod 9 = 0 then
515                AddSet (ppds, 6);
516                AddSet (orders, 9);
517            fi;
518            UniteSet(invariants,ppds);
519            UniteSet(combs, Combinations (ppds, 2));
520        od;
521        newv1 := Maximum (invariants);
522    until newv1 = v1;
523    return [invariants, combs, orders];
524end; # ArtinInvariants
525
526
527RECOG.LieType := function (G, p, orders, Nmr)
528    local   temp,  invar,  combs,  orders2,  v1,  v2,  w,  v3,  e,  m,
529            bound,  combs2;
530
531    #   P := RandomProcess ( G );
532    temp := RECOG.ArtinInvariants (G, p, Nmr);
533    invar := temp[1];
534    combs := temp[2];
535    orders2 := temp[3];
536   UniteSet(orders, orders2);
537
538   v1 := Maximum (invar);
539   RemoveSet(invar, v1);
540
541   if v1 = 2 then
542      return RECOG.VerifyOrders ("L",2, p, orders);
543   fi;
544
545   if v1 = 3 then
546      if p > 2 then
547         return RECOG.VerifyOrders ("L",3, p, orders);
548      elif 8 in orders then
549         return RECOG.VerifyOrders ("U",3, 3, orders);
550      else
551         return RECOG.VerifyOrders ("L",3, 2, orders);
552      fi;
553   fi;
554
555
556   if v1 = 4 then
557      if 3 in invar then
558         if p > 2 then
559            return RECOG.VerifyOrders ("L",4, p, orders);
560         elif 15 in orders then
561            return RECOG.VerifyOrders ("L",4, 2, orders);
562         else
563            return RECOG.VerifyOrders ("L",3, 4, orders);
564         fi;
565      else
566         return RECOG.PSLvsPSP (G, [1, 2, 4], p, RECOG.LieTypeSampleSize,
567                   RECOG.LieTypeNmrTrials, orders);
568      fi;
569   fi;  # v1 = 4
570
571   v2 := Maximum (invar);
572   w := v1 / (v1 - v2);
573
574#v1; v2; w; invar; orders;
575   if v1 = 12 and v2 = 4 and p = 2 then
576      if 21 in orders then
577         return RECOG.VerifyOrders ("G",2, 4, orders);
578      elif 16 in orders then
579         return RECOG.VerifyOrders ("2F",4, 2, orders);
580      elif 7 in orders then
581         return RECOG.VerifyOrders ("2B",2, 8, orders);
582      elif 15 in orders then
583         return RECOG.VerifyOrders ("U",3, 4, orders);
584      else
585          return "RO_CONTRADICTION";
586      fi;
587   fi;  # v2 = 4
588
589   RemoveSet(invar,v2);
590   if Length(invar)  = 0 then
591       return "RO_Unknown";
592   fi;
593   v3 := Maximum (invar);
594
595#printf"p, v1, v2, v3: %o %o %o %o;",p,v1,v2,v3; invar; combs; orders;
596   if v1 mod 2 = 1 then
597      e := v1 - v2;
598      if v1 mod e <> 0 then
599         return "RO_CONTRADICTION";
600      fi;
601      m := v1/e;
602      if v3 <> e* (m-2) then
603          return "RO_CONTRADICTION";
604      fi;
605      return RECOG.VerifyOrders ("L", m, p^e, orders);
606   fi;
607
608   if w = 3/2 then
609      if p = 2 and not 3 in orders then
610         if v1 mod 8 <> 4 then
611            return "RO_CONTRADICTION";
612         fi;
613         return RECOG.VerifyOrders ("2B",2,2^(v1 / 4), orders);
614      fi;
615      if v1 mod 6 <> 0 then
616         return "RO_CONTRADICTION";
617      fi;
618      if p = 3 and not 4 in orders then
619         if v1 > 6 then
620            if v1 mod 12 <> 6 then
621               return "RO_CONTRADICTION";
622            fi;
623            return RECOG.VerifyOrders ("2G",2, 3^(v1 / 6), orders);
624         else
625            return RECOG.VerifyOrders ("L",2, 8, orders);
626         fi;
627      fi;
628      return RECOG.VerifyOrders ("U",3, p^(v1 / 6), orders);
629   fi;
630
631   if w = 4/3 then
632      if p = 2 and v1 mod 8 = 4 then
633         return RECOG.VerifyOrders ("2B",2, 2^(v1 / 4), orders);
634      fi;
635      return "RO_CONTRADICTION";
636   fi;
637
638   if w = 2 then  # exceptional groups
639      if v1 mod 12 = 0 and not ([v1 / 3, v1] in combs) then
640         if 4 * v3 = v1 then
641            return RECOG.VerifyOrders ("3D",4, p^(v1 / 12), orders);
642         elif (v1 / 4) in invar or (p = 2 and v1 = 24) then
643            return RECOG.VerifyOrders ("G",2, p^(v1 / 6), orders);
644         else
645            if p = 2 and v1 mod 24 = 12 and 12*v3 = 4*v1 then
646               return RECOG.VerifyOrders ("2F",4,2^(v1 / 12), orders);
647            else return "RO_CONTRADICTION";
648            fi;
649         fi;
650
651  #    /* next clause is replacement for error in draft of paper */
652      elif v1 mod 12 = 6 and Maximum (orders) <= p^(v1/3) + p^(v1/6) + 1 then
653         return RECOG.VerifyOrders ("G",2, p^(v1 / 6), orders);
654      fi;
655
656      if v1 mod 4 = 2 then
657         return RECOG.VerifyOrders ("L",2,p^(v1 / 2), orders);
658      else
659         return RECOG.PSLvsPSP (G, Union(invar,[v1, v2]),p^(v1 / 4),
660                  RECOG.LieTypeSampleSize, RECOG.LieTypeNmrTrials, orders);
661      fi;
662   fi;  # w = 2
663
664#printf"p, v1, v2, v3: %o %o %o %o;",p,v1,v2,v3; invar; combs; orders;
665   if w = 3 then
666      if v1 mod 18 = 0 and 18 * v3 = 10 * v1 then
667         if 8* (v1 / 18) in invar then
668            return RECOG.VerifyOrders ("2E",6, p^(v1 / 18), orders);
669         else return "RO_OTHER";
670         fi;
671      elif v1 mod 12 = 0 then
672         if v1 > 12 or p > 2 then
673            if v1 = 2 * v3 and not ([v1 / 2, v1] in combs)
674               and not ([v1 / 3, v1] in combs) then
675               return RECOG.VerifyOrders ("F",4, p^(v1 / 12), orders);
676            fi;
677         elif 9 in orders and not ([4, 12] in combs) then
678            return RECOG.VerifyOrders ("F",4, 2, orders);
679         fi;
680      fi;
681   fi;  # w = 3
682
683   if w = 4 and 8 * v1 = 12 * v3 then
684      if v1 mod 12 = 0 then
685         return RECOG.VerifyOrders ("E",6, p^(v1 / 12), orders);
686      fi;
687      return "RO_CONTRADICTION";
688   fi;
689
690   if w = 9/2 and 12 * v1 = 18 * v3 then
691      if v1 mod 18 = 0 then
692         return RECOG.VerifyOrders ("E",7, p^(v1 / 18), orders);
693      fi;
694      return "RO_CONTRADICTION";
695   fi;
696
697   if w = 5 and 20 * v1 = 30 * v3 then
698      if v1 mod 30 = 0 then
699         return RECOG.VerifyOrders ("E",8, p^(v1 / 30), orders);
700      fi;
701      return "RO_CONTRADICTION";
702   fi;   # exceptional groups
703
704   if v1 mod (v1 - v2) <> 0 then   # unitary groups
705      if (v1-v2) mod 4 <> 0  or  2 * v1 mod (v1 - v2) <> 0 then
706          return "RO_OTHER";
707      fi;
708      e := (v1-v2) / 4;
709      m := (2 * v1) / (v1 - v2);
710      if ((m + 1) mod 4 = 0 and e * (m + 1) in invar) or
711        ((m + 1) mod 4 <> 0 and e * (m + 1) / 2 in invar) then
712            if (m > 7 and v2-v3 = 4*e) or (m <= 7 and v2-v3 = 2*e) then
713               return RECOG.VerifyOrders ("U", m + 1, p^e, orders);
714            fi;
715      else
716         if (m > 5 and v2-v3 = 4*e) or (m = 5 and v2-v3 = 2*e) then
717            return RECOG.VerifyOrders ("U", m, p^e, orders);
718         fi;
719      fi;
720      return "RO_OTHER";
721   fi;   # unitary groups
722
723#printf"1: v1 v2 v3 = %o %o %o;;",v1, v2, v3; invar;
724   if (v1 - v2) mod 2 <> 0 then
725      e := v1 - v2;  m := v1 / (v1 - v2);
726      if v3 = e* (m-2) or (p = 2 and e* (m-2) = 6) or (m <= 3) then
727         return RECOG.VerifyOrders ("L", m, p^e, orders);
728      else
729         return "RO_OTHER";
730      fi;
731   fi;
732
733   e := (v1 - v2) / 2; m := v1 / (v1 - v2);  # only classical grps remain
734
735   if p = 2 and e * m = 6 and e <= 2 and 91 in orders then
736      if v3 = 10-2*e  or  m = 3 then
737         return RECOG.VerifyOrders ("L", m, 2^(2 * e), orders);
738      else
739         return "RO_OTHER";
740      fi;
741   fi;
742
743   if Set([m * e, v1]) in combs then
744      if v3 = 2*e* (m-2) or m <= 3 then
745         return RECOG.VerifyOrders ("L", m, p^(2 * e), orders);
746      else
747         return "RO_OTHER";
748      fi;
749   fi;
750
751   if m = 3 then
752      if 3 * v3 = v1 then
753         return RECOG.VerifyOrders ("U",4, p^(v1 / 6), orders);
754      else
755         if p^e = 2 then
756            return RECOG.OPlus82vsS62 (G, orders, RECOG.LieTypeSampleSize);
757         fi;
758         if p^e = 3 then
759            return RECOG.OPlus83vsO73vsSP63 (G,orders,RECOG.LieTypeSampleSize);
760         else
761            return RECOG.OPlus8vsO7vsSP6 (G,orders,p,e,RECOG.LieTypeSampleSize);
762         fi;
763      fi;
764   fi;
765
766   if v3 <> 2*e* (m-2) and (m > 4 or v3 <> 5*e) then   # wrong characteristic
767      return "RO_OTHER";
768   fi;
769
770   if IsMatrixGroup(G) then
771       bound := 5*DimensionOfMatrixGroup(G);
772   else
773       bound := 100;
774   fi;
775   temp := RECOG.ArtinInvariants (G, p, bound);
776   invar := temp[1]; combs2 := temp[2]; orders2 := temp[3];
777   combs := Union(combs, combs2);
778   orders := Union(orders, orders2);
779   if m mod 2 = 0 then
780      if [m * e, (m + 2) * e] in combs then
781          return RECOG.VerifyOrders ("O^+", 2 * m + 2, p^e, orders);
782      elif m = 4 then
783         return RECOG.OMinus8vsSPvsO(G,v1,p,e,orders,RECOG.LieTypeSampleSize,
784                                     RECOG.LieTypeNmrTrials);
785      else #/* m >= 6 */
786         if [ (m - 2) * e, (m + 2) * e] in combs then
787            if p = 2 then
788               return RECOG.VerifyOrders ("S", 2 * m, 2^e, orders);
789            else
790               return RECOG.DistinguishSpO (G, m, p, e, orders);
791            fi;
792         else
793            return RECOG.VerifyOrders ("O^-", 2*m, p^e, orders);
794         fi;
795      fi;  # m even
796   elif [(m - 1) * e, (m + 3) * e] in combs then
797      return RECOG.VerifyOrders ("O^+", 2 * m + 2, p^e, orders);
798   elif [(m - 1) * e, (m + 1) * e] in combs then
799      if p = 2 then
800         return RECOG.VerifyOrders ("S", 2 * m, 2^e, orders);
801      fi;
802      # p <> 2 case
803      return RECOG.DistinguishSpO (G, m, p, e, orders);
804   else
805      return RECOG.VerifyOrders ("O^-", 2 * m, p^e, orders);
806   fi;
807
808   return "RO_undecided";
809end;
810
811FindHomMethodsProjective.LieTypeNonConstr := function(ri,G)
812    local count,dim,f,i,ords,p,q,r,res;
813    RECOG.SetPseudoRandomStamp(G,"LieTypeNonConstr");
814    dim := ri!.dimension;
815    f := ri!.field;
816    q := Size(f);
817    p := Characteristic(f);
818
819    count := 0;
820    ords := Set(ri!.simplesoclerando);
821    while true do   # will be left by return
822        r := RECOG.LieType(ri!.simplesocle,p,ords,30+10*dim);
823        if not(IsString(r)) or r{[1..3]} <> "RO_" then
824            # We found something:
825            Info(InfoRecog,2,"LieTypeNonConstr: found ",r,
826                 ", lookup up hints...");
827            ri!.comment := Concatenation("_",r);
828            res := LookupHintForSimple(ri,G,r);
829            # FIXME: LookupHintForSimple is for sporadics... So why do we use it here?
830            if res = true then
831                return Success;
832            fi;
833            Info(InfoRecog,2,"LieTypeNonConstr: giving up.");
834            return fail;
835        fi;
836        count := count + 1;
837        if count > 3 then
838            Info(InfoRecog,2,"LieTypeNonConstr: giving up...");
839            return TemporaryFailure;
840        fi;
841        Info(InfoRecog,2,"LieTypeNonConstr: need more element orders...");
842        for i in [1..dim] do
843            AddSet(ords,RandomElmOrd(ri,"LieTypeNonConstr",false).order);
844        od;
845    od;
846end;
847
848##
849##  This program is free software: you can redistribute it and/or modify
850##  it under the terms of the GNU General Public License as published by
851##  the Free Software Foundation, either version 3 of the License, or
852##  (at your option) any later version.
853##
854##  This program is distributed in the hope that it will be useful,
855##  but WITHOUT ANY WARRANTY; without even the implied warranty of
856##  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
857##  GNU General Public License for more details.
858##
859##  You should have received a copy of the GNU General Public License
860##  along with this program.  If not, see <http://www.gnu.org/licenses/>.
861##
862