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