1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
|
<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<title>GAP (AtlasRep) - Chapter 6: New GAP Objects and Utility Functions provided by the
AtlasRep Package</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
<script src="manual.js" type="text/javascript"></script>
<script type="text/javascript">overwriteStyle();</script>
</head>
<body class="chap6" onload="jscontent()">
<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chap7.html">7</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<div class="chlinkprevnexttop"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap5.html">[Previous Chapter]</a> <a href="chap7.html">[Next Chapter]</a> </div>
<p id="mathjaxlink" class="pcenter"><a href="chap6_mj.html">[MathJax on]</a></p>
<p><a id="X83827EDB7D36C407" name="X83827EDB7D36C407"></a></p>
<div class="ChapSects"><a href="chap6.html#X83827EDB7D36C407">6 <span class="Heading">New <strong class="pkg">GAP</strong> Objects and Utility Functions provided by the
<strong class="pkg">AtlasRep</strong> Package</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap6.html#X8121E9567A7137C9">6.1 <span class="Heading">Straight Line Decisions</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X8787E2EC7DB85A89">6.1-1 IsStraightLineDecision</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X82AFAD9F7FA5CE8A">6.1-2 LinesOfStraightLineDecision</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7B1A43427BD97FDF">6.1-3 NrInputsOfStraightLineDecision</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X82A3632782E45F35">6.1-4 ScanStraightLineDecision</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X825C4E4180F3D989">6.1-5 StraightLineDecision</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7E7B328A84685480">6.1-6 ResultOfStraightLineDecision</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7C94ECAC8583CEAE">6.1-7 <span class="Heading">Semi-Presentations and Presentations</span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7C13D08C7D55E20A">6.1-8 AsStraightLineDecision</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7EA613C57DDC67D5">6.1-9 StraightLineProgramFromStraightLineDecision</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap6.html#X7BE856BC785A9E8F">6.2 <span class="Heading">Black Box Programs</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X87CAF2DE870D0E3B">6.2-1 IsBBoxProgram</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7EA20532868F9863">6.2-2 ScanBBoxProgram</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7D211A5D8602B330">6.2-3 RunBBoxProgram</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X869BACFB80A3CC87">6.2-4 ResultOfBBoxProgram</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X826ACFE887E0B6B8">6.2-5 AsBBoxProgram</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7D36DFA87C8B2C48">6.2-6 AsStraightLineProgram</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap6.html#X87E1F08D80C9E069">6.3 <span class="Heading">Representations of Minimal Degree</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7DC66D8282B2BB7F">6.3-1 MinimalRepresentationInfo</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7E1B76DC86A8C405">6.3-2 MinimalRepresentationInfoData</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X79C4C9F683E919C9">6.3-3 SetMinimalRepresentationInfo</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7FC33DFF8481F8D1">6.3-4 <span class="Heading">Criteria Used to Compute Minimality Information</span></a>
</span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap6.html#X7E5CB1637F127B2E">6.4 <span class="Heading">A JSON Interface</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X7870BBB184574D18">6.4-1 <span class="Heading">Why JSON?</span></a>
</span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X87A307D284975AA9">6.4-2 AGR.JsonText</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap6.html#X79DF4DC67DCFE27B">6.4-3 AGR.GapObjectOfJsonText</a></span>
</div></div>
</div>
<h3>6 <span class="Heading">New <strong class="pkg">GAP</strong> Objects and Utility Functions provided by the
<strong class="pkg">AtlasRep</strong> Package</span></h3>
<p>This chapter describes <strong class="pkg">GAP</strong> objects and functions that are provided by the <strong class="pkg">AtlasRep</strong> package but that might be of general interest.</p>
<p>The new objects are straight line decisions (see Section <a href="chap6.html#X8121E9567A7137C9"><span class="RefLink">6.1</span></a>) and black box programs (see Section <a href="chap6.html#X7BE856BC785A9E8F"><span class="RefLink">6.2</span></a>).</p>
<p>The new functions are concerned with representations of minimal degree, see Section <a href="chap6.html#X87E1F08D80C9E069"><span class="RefLink">6.3</span></a>, and a JSON interface, see Section <a href="chap6.html#X7E5CB1637F127B2E"><span class="RefLink">6.4</span></a>.</p>
<p><a id="X8121E9567A7137C9" name="X8121E9567A7137C9"></a></p>
<h4>6.1 <span class="Heading">Straight Line Decisions</span></h4>
<p><em>Straight line decisions</em> are similar to straight line programs (see Section <a href="../../../doc/ref/chap37.html#X7DC99E4284093FBB"><span class="RefLink">Reference: Straight Line Programs</span></a>) but return <code class="keyw">true</code> or <code class="keyw">false</code>. A straight line decision checks whether its inputs have some property. An important example is to check whether a given list of group generators is in fact a list of standard generators (cf. Section<a href="chap3.html#X795DB7E486E0817D"><span class="RefLink">3.3</span></a>) for this group.</p>
<p>A straight line decision in <strong class="pkg">GAP</strong> is represented by an object in the filter <code class="func">IsStraightLineDecision</code> (<a href="chap6.html#X8787E2EC7DB85A89"><span class="RefLink">6.1-1</span></a>) that stores a list of <q>lines</q> each of which has one of the following three forms.</p>
<ol>
<li><p>a nonempty dense list <span class="SimpleMath">l</span> of integers,</p>
</li>
<li><p>a pair <span class="SimpleMath">[ l, i ]</span> where <span class="SimpleMath">l</span> is a list of form 1. and <span class="SimpleMath">i</span> is a positive integer,</p>
</li>
<li><p>a list <span class="SimpleMath">[</span> <code class="code">"Order"</code><span class="SimpleMath">, i, n ]</span> where <span class="SimpleMath">i</span> and <span class="SimpleMath">n</span> are positive integers.</p>
</li>
</ol>
<p>The first two forms have the same meaning as for straight line programs (see Section <a href="../../../doc/ref/chap37.html#X7DC99E4284093FBB"><span class="RefLink">Reference: Straight Line Programs</span></a>), the last form means a check whether the element stored at the <span class="SimpleMath">i</span>-th label has the order <span class="SimpleMath">n</span>.</p>
<p>For the meaning of the list of lines, see <code class="func">ResultOfStraightLineDecision</code> (<a href="chap6.html#X7E7B328A84685480"><span class="RefLink">6.1-6</span></a>).</p>
<p>Straight line decisions can be constructed using <code class="func">StraightLineDecision</code> (<a href="chap6.html#X825C4E4180F3D989"><span class="RefLink">6.1-5</span></a>), defining attributes for straight line decisions are <code class="func">NrInputsOfStraightLineDecision</code> (<a href="chap6.html#X7B1A43427BD97FDF"><span class="RefLink">6.1-3</span></a>) and <code class="func">LinesOfStraightLineDecision</code> (<a href="chap6.html#X82AFAD9F7FA5CE8A"><span class="RefLink">6.1-2</span></a>), an operation for straight line decisions is <code class="func">ResultOfStraightLineDecision</code> (<a href="chap6.html#X7E7B328A84685480"><span class="RefLink">6.1-6</span></a>).</p>
<p>Special methods applicable to straight line decisions are installed for the operations <code class="func">Display</code> (<a href="../../../doc/ref/chap6.html#X83A5C59278E13248"><span class="RefLink">Reference: Display</span></a>), <code class="func">IsInternallyConsistent</code> (<a href="../../../doc/ref/chap12.html#X7F6C5C3287E8B816"><span class="RefLink">Reference: IsInternallyConsistent</span></a>), <code class="func">PrintObj</code> (<a href="../../../doc/ref/chap6.html#X815BF22186FD43C9"><span class="RefLink">Reference: PrintObj</span></a>), and <code class="func">ViewObj</code> (<a href="../../../doc/ref/chap6.html#X815BF22186FD43C9"><span class="RefLink">Reference: ViewObj</span></a>).</p>
<p>For a straight line decision <var class="Arg">prog</var>, the default <code class="func">Display</code> (<a href="../../../doc/ref/chap6.html#X83A5C59278E13248"><span class="RefLink">Reference: Display</span></a>) method prints the interpretation of <var class="Arg">prog</var> as a sequence of assignments of associative words and of order checks; a record with components <code class="code">gensnames</code> (with value a list of strings) and <code class="code">listname</code> (a string) may be entered as second argument of <code class="func">Display</code> (<a href="../../../doc/ref/chap6.html#X83A5C59278E13248"><span class="RefLink">Reference: Display</span></a>), in this case these names are used, the default for <code class="code">gensnames</code> is <code class="code">[ g1, g2, </code><span class="SimpleMath">...</span><code class="code"> ]</code>, the default for <var class="Arg">listname</var> is <span class="SimpleMath">r</span>.</p>
<p><a id="X8787E2EC7DB85A89" name="X8787E2EC7DB85A89"></a></p>
<h5>6.1-1 IsStraightLineDecision</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsStraightLineDecision</code>( <var class="Arg">obj</var> )</td><td class="tdright">( category )</td></tr></table></div>
<p>Each straight line decision in <strong class="pkg">GAP</strong> lies in the filter <code class="func">IsStraightLineDecision</code>.</p>
<p><a id="X82AFAD9F7FA5CE8A" name="X82AFAD9F7FA5CE8A"></a></p>
<h5>6.1-2 LinesOfStraightLineDecision</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ LinesOfStraightLineDecision</code>( <var class="Arg">prog</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: the list of lines that define the straight line decision.</p>
<p>This defining attribute for the straight line decision <var class="Arg">prog</var> (see <code class="func">IsStraightLineDecision</code> (<a href="chap6.html#X8787E2EC7DB85A89"><span class="RefLink">6.1-1</span></a>)) corresponds to <code class="func">LinesOfStraightLineProgram</code> (<a href="../../../doc/ref/chap37.html#X81A8AFC47F8E4B91"><span class="RefLink">Reference: LinesOfStraightLineProgram</span></a>) for straight line programs.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">dec:= StraightLineDecision( [ [ [ 1, 1, 2, 1 ], 3 ],</span>
<span class="GAPprompt">></span> <span class="GAPinput">[ "Order", 1, 2 ], [ "Order", 2, 3 ], [ "Order", 3, 5 ] ] );</span>
<straight line decision>
<span class="GAPprompt">gap></span> <span class="GAPinput">LinesOfStraightLineDecision( dec );</span>
[ [ [ 1, 1, 2, 1 ], 3 ], [ "Order", 1, 2 ], [ "Order", 2, 3 ],
[ "Order", 3, 5 ] ]
</pre></div>
<p><a id="X7B1A43427BD97FDF" name="X7B1A43427BD97FDF"></a></p>
<h5>6.1-3 NrInputsOfStraightLineDecision</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NrInputsOfStraightLineDecision</code>( <var class="Arg">prog</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: the number of inputs required for the straight line decision.</p>
<p>This defining attribute corresponds to <code class="func">NrInputsOfStraightLineProgram</code> (<a href="../../../doc/ref/chap37.html#X820A592881D57802"><span class="RefLink">Reference: NrInputsOfStraightLineProgram</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">NrInputsOfStraightLineDecision( dec );</span>
2
</pre></div>
<p><a id="X82A3632782E45F35" name="X82A3632782E45F35"></a></p>
<h5>6.1-4 ScanStraightLineDecision</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ScanStraightLineDecision</code>( <var class="Arg">string</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a record containing the straight line decision, or <code class="keyw">fail</code>.</p>
<p>Let <var class="Arg">string</var> be a string that encodes a straight line decision in the sense that it consists of the lines listed for <code class="func">ScanStraightLineProgram</code> (<a href="chap7.html#X7D6617E47B013A37"><span class="RefLink">7.4-1</span></a>), except that <code class="code">oup</code> lines are not allowed, and instead lines of the following form may occur.</p>
<dl>
<dt><strong class="Mark"><code class="code">chor </code><span class="SimpleMath">a</span> <span class="SimpleMath">b</span></strong></dt>
<dd><p>means that it is checked whether the order of the element at label <span class="SimpleMath">a</span> is <span class="SimpleMath">b</span>.</p>
</dd>
</dl>
<p><code class="func">ScanStraightLineDecision</code> returns a record containing as the value of its component <code class="code">program</code> the corresponding <strong class="pkg">GAP</strong> straight line decision (see <code class="func">IsStraightLineDecision</code> (<a href="chap6.html#X8787E2EC7DB85A89"><span class="RefLink">6.1-1</span></a>)) if the input string satisfies the syntax rules stated above, and returns <code class="keyw">fail</code> otherwise. In the latter case, information about the first corrupted line of the program is printed if the info level of <code class="func">InfoCMeatAxe</code> (<a href="chap7.html#X78601C3A87921E08"><span class="RefLink">7.1-2</span></a>) is at least <span class="SimpleMath">1</span>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">str:= "inp 2\nchor 1 2\nchor 2 3\nmu 1 2 3\nchor 3 5";;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">prg:= ScanStraightLineDecision( str );</span>
rec( program := <straight line decision> )
<span class="GAPprompt">gap></span> <span class="GAPinput">prg:= prg.program;;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display( prg );</span>
# input:
r:= [ g1, g2 ];
# program:
if Order( r[1] ) <> 2 then return false; fi;
if Order( r[2] ) <> 3 then return false; fi;
r[3]:= r[1]*r[2];
if Order( r[3] ) <> 5 then return false; fi;
# return value:
true
</pre></div>
<p><a id="X825C4E4180F3D989" name="X825C4E4180F3D989"></a></p>
<h5>6.1-5 StraightLineDecision</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ StraightLineDecision</code>( <var class="Arg">lines</var>[, <var class="Arg">nrgens</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ StraightLineDecisionNC</code>( <var class="Arg">lines</var>[, <var class="Arg">nrgens</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: the straight line decision given by the list of lines.</p>
<p>Let <var class="Arg">lines</var> be a list of lists that defines a unique straight line decision (see <code class="func">IsStraightLineDecision</code> (<a href="chap6.html#X8787E2EC7DB85A89"><span class="RefLink">6.1-1</span></a>)); in this case <code class="func">StraightLineDecision</code> returns this program, otherwise an error is signalled. The optional argument <var class="Arg">nrgens</var> specifies the number of input generators of the program; if a list of integers (a line of form 1. in the definition above) occurs in <var class="Arg">lines</var> then this number is not determined by <var class="Arg">lines</var> and therefore <em>must</em> be specified by the argument <var class="Arg">nrgens</var>; if not then <code class="func">StraightLineDecision</code> returns <code class="keyw">fail</code>.</p>
<p><code class="func">StraightLineDecisionNC</code> does the same as <code class="func">StraightLineDecision</code>, except that the internal consistency of the program is not checked.</p>
<p><a id="X7E7B328A84685480" name="X7E7B328A84685480"></a></p>
<h5>6.1-6 ResultOfStraightLineDecision</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ResultOfStraightLineDecision</code>( <var class="Arg">prog</var>, <var class="Arg">gens</var>[, <var class="Arg">orderfunc</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> if all checks succeed, otherwise <code class="keyw">false</code>.</p>
<p><code class="func">ResultOfStraightLineDecision</code> evaluates the straight line decision (see <code class="func">IsStraightLineDecision</code> (<a href="chap6.html#X8787E2EC7DB85A89"><span class="RefLink">6.1-1</span></a>)) <var class="Arg">prog</var> at the group elements in the list <var class="Arg">gens</var>.</p>
<p>The function for computing the order of a group element can be given as the optional argument <var class="Arg">orderfunc</var>. For example, this may be a function that gives up at a certain limit if one has to be aware of extremely huge orders in failure cases.</p>
<p>The <em>result</em> of a straight line decision with lines <span class="SimpleMath">p_1, p_2, ..., p_k</span> when applied to <var class="Arg">gens</var> is defined as follows.</p>
<dl>
<dt><strong class="Mark">(a)</strong></dt>
<dd><p>First a list <span class="SimpleMath">r</span> of intermediate values is initialized with a shallow copy of <var class="Arg">gens</var>.</p>
</dd>
<dt><strong class="Mark">(b)</strong></dt>
<dd><p>For <span class="SimpleMath">i ≤ k</span>, before the <span class="SimpleMath">i</span>-th step, let <span class="SimpleMath">r</span> be of length <span class="SimpleMath">n</span>. If <span class="SimpleMath">p_i</span> is the external representation of an associative word in the first <span class="SimpleMath">n</span> generators then the image of this word under the homomorphism that is given by mapping <span class="SimpleMath">r</span> to these first <span class="SimpleMath">n</span> generators is added to <span class="SimpleMath">r</span>. If <span class="SimpleMath">p_i</span> is a pair <span class="SimpleMath">[ l, j ]</span>, for a list <span class="SimpleMath">l</span>, then the same element is computed, but instead of being added to <span class="SimpleMath">r</span>, it replaces the <span class="SimpleMath">j</span>-th entry of <span class="SimpleMath">r</span>. If <span class="SimpleMath">p_i</span> is a triple <span class="SimpleMath">[</span><code class="code">"Order"</code><span class="SimpleMath">, i, n ]</span> then it is checked whether the order of <span class="SimpleMath">r[i]</span> is <span class="SimpleMath">n</span>; if not then <code class="keyw">false</code> is returned immediately.</p>
</dd>
<dt><strong class="Mark">(c)</strong></dt>
<dd><p>If all <span class="SimpleMath">k</span> lines have been processed and no order check has failed then <code class="keyw">true</code> is returned.</p>
</dd>
</dl>
<p>Here are some examples.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">dec:= StraightLineDecision( [ ], 1 );</span>
<straight line decision>
<span class="GAPprompt">gap></span> <span class="GAPinput">ResultOfStraightLineDecision( dec, [ () ] );</span>
true
</pre></div>
<p>The above straight line decision <code class="code">dec</code> returns <code class="keyw">true</code> –for <em>any</em> input of the right length.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">dec:= StraightLineDecision( [ [ [ 1, 1, 2, 1 ], 3 ],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [ "Order", 1, 2 ], [ "Order", 2, 3 ], [ "Order", 3, 5 ] ] );</span>
<straight line decision>
<span class="GAPprompt">gap></span> <span class="GAPinput">LinesOfStraightLineDecision( dec );</span>
[ [ [ 1, 1, 2, 1 ], 3 ], [ "Order", 1, 2 ], [ "Order", 2, 3 ],
[ "Order", 3, 5 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">ResultOfStraightLineDecision( dec, [ (), () ] );</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">ResultOfStraightLineDecision( dec, [ (1,2)(3,4), (1,4,5) ] );</span>
true
</pre></div>
<p>The above straight line decision admits two inputs; it tests whether the orders of the inputs are <span class="SimpleMath">2</span> and <span class="SimpleMath">3</span>, and the order of their product is <span class="SimpleMath">5</span>.</p>
<p><a id="X7C94ECAC8583CEAE" name="X7C94ECAC8583CEAE"></a></p>
<h5>6.1-7 <span class="Heading">Semi-Presentations and Presentations</span></h5>
<p>We can associate a <em>finitely presented group</em> <span class="SimpleMath">F / R</span> to each straight line decision <var class="Arg">dec</var>, say, as follows. The free generators of the free group <span class="SimpleMath">F</span> are in bijection with the inputs, and the defining relators generating <span class="SimpleMath">R</span> as a normal subgroup of <span class="SimpleMath">F</span> are given by those words <span class="SimpleMath">w^k</span> for which <var class="Arg">dec</var> contains a check whether the order of <span class="SimpleMath">w</span> equals <span class="SimpleMath">k</span>.</p>
<p>So if <var class="Arg">dec</var> returns <code class="keyw">true</code> for the input list <span class="SimpleMath">[ g_1, g_2, ..., g_n ]</span> then mapping the free generators of <span class="SimpleMath">F</span> to the inputs defines an epimorphism <span class="SimpleMath">Φ</span> from <span class="SimpleMath">F</span> to the group <span class="SimpleMath">G</span>, say, that is generated by these inputs, such that <span class="SimpleMath">R</span> is contained in the kernel of <span class="SimpleMath">Φ</span>.</p>
<p>(Note that <q>satisfying <var class="Arg">dec</var></q> is a stronger property than <q>satisfying a presentation</q>. For example, <span class="SimpleMath">⟨ x ∣ x^2 = x^3 = 1 ⟩</span> is a presentation for the trivial group, but the straight line decision that checks whether the order of <span class="SimpleMath">x</span> is both <span class="SimpleMath">2</span> and <span class="SimpleMath">3</span> clearly always returns <code class="keyw">false</code>.)</p>
<p><strong class="pkg">AtlasRep</strong> supports the following two kinds of straight line decisions.</p>
<ul>
<li><p>A <em>presentation</em> is a straight line decision <var class="Arg">dec</var> that is defined for a set of standard generators of a group <span class="SimpleMath">G</span> and that returns <code class="keyw">true</code> if and only if the list of inputs is in fact a sequence of such standard generators for <span class="SimpleMath">G</span>. In other words, the relators derived from the order checks in the way described above are defining relators for <span class="SimpleMath">G</span>, and moreover these relators are words in terms of standard generators. (In particular the kernel of the map <span class="SimpleMath">Φ</span> equals <span class="SimpleMath">R</span> whenever <var class="Arg">dec</var> returns <code class="keyw">true</code>.)</p>
</li>
<li><p>A <em>semi-presentation</em> is a straight line decision <var class="Arg">dec</var> that is defined for a set of standard generators of a group <span class="SimpleMath">G</span> and that returns <code class="keyw">true</code> for a list of inputs <em>that is known to generate a group isomorphic with <span class="SimpleMath">G</span></em> if and only if these inputs form in fact a sequence of standard generators for <span class="SimpleMath">G</span>. In other words, the relators derived from the order checks in the way described above are <em>not necessarily defining relators</em> for <span class="SimpleMath">G</span>, but if we assume that the <span class="SimpleMath">g_i</span> generate <span class="SimpleMath">G</span> then they are standard generators. (In particular, <span class="SimpleMath">F / R</span> may be a larger group than <span class="SimpleMath">G</span> but in this case <span class="SimpleMath">Φ</span> maps the free generators of <span class="SimpleMath">F</span> to standard generators of <span class="SimpleMath">G</span>.)</p>
<p>More about semi-presentations can be found in <a href="chapBib.html#biBNW05">[NW05]</a>.</p>
</li>
</ul>
<p>Available presentations and semi-presentations are listed by <code class="func">DisplayAtlasInfo</code> (<a href="chap3.html#X79DACFFA7E2D1A99"><span class="RefLink">3.5-1</span></a>), they can be accessed via <code class="func">AtlasProgram</code> (<a href="chap3.html#X801F2E657C8A79ED"><span class="RefLink">3.5-4</span></a>). (Clearly each presentation is also a semi-presentation. So a semi-presentation for some standard generators of a group is regarded as available whenever a presentation for these standard generators and this group is available.)</p>
<p>Note that different groups can have the same semi-presentation. We illustrate this with an example that is mentioned in <a href="chapBib.html#biBNW05">[NW05]</a>. The groups <span class="SimpleMath">L_2(7) ≅ L_3(2)</span> and <span class="SimpleMath">L_2(8)</span> are generated by elements of the orders <span class="SimpleMath">2</span> and <span class="SimpleMath">3</span> such that their product has order <span class="SimpleMath">7</span>, and no further conditions are necessary to define standard generators.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">check:= AtlasProgram( "L2(8)", "check" );</span>
rec( groupname := "L2(8)",
identifier := [ "L2(8)", "L28G1-check1", 1, 1 ],
program := <straight line decision>, standardization := 1,
version := "1" )
<span class="GAPprompt">gap></span> <span class="GAPinput">gens:= AtlasGenerators( "L2(8)", 1 );</span>
rec( charactername := "1a+8a", constituents := [ 1, 6 ],
contents := "core",
generators := [ (1,2)(3,4)(6,7)(8,9), (1,3,2)(4,5,6)(7,8,9) ],
groupname := "L2(8)", id := "",
identifier := [ "L2(8)", [ "L28G1-p9B0.m1", "L28G1-p9B0.m2" ], 1, 9
], isPrimitive := true, maxnr := 1, p := 9, rankAction := 2,
repname := "L28G1-p9B0", repnr := 1, size := 504,
stabilizer := "2^3:7", standardization := 1, transitivity := 3,
type := "perm" )
<span class="GAPprompt">gap></span> <span class="GAPinput">ResultOfStraightLineDecision( check.program, gens.generators );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">gens:= AtlasGenerators( "L3(2)", 1 );</span>
rec( contents := "core", generators := [ (2,4)(3,5), (1,2,3)(5,6,7) ],
groupname := "L3(2)", id := "a",
identifier := [ "L3(2)", [ "L27G1-p7aB0.m1", "L27G1-p7aB0.m2" ], 1,
7 ], isPrimitive := true, maxnr := 1, p := 7, rankAction := 2,
repname := "L27G1-p7aB0", repnr := 1, size := 168,
stabilizer := "S4", standardization := 1, transitivity := 2,
type := "perm" )
<span class="GAPprompt">gap></span> <span class="GAPinput">ResultOfStraightLineDecision( check.program, gens.generators );</span>
true
</pre></div>
<p><a id="X7C13D08C7D55E20A" name="X7C13D08C7D55E20A"></a></p>
<h5>6.1-8 AsStraightLineDecision</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AsStraightLineDecision</code>( <var class="Arg">bbox</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: an equivalent straight line decision for the given black box program, or <code class="keyw">fail</code>.</p>
<p>For a black box program (see <code class="func">IsBBoxProgram</code> (<a href="chap6.html#X87CAF2DE870D0E3B"><span class="RefLink">6.2-1</span></a>)) <var class="Arg">bbox</var>, <code class="func">AsStraightLineDecision</code> returns a straight line decision (see <code class="func">IsStraightLineDecision</code> (<a href="chap6.html#X8787E2EC7DB85A89"><span class="RefLink">6.1-1</span></a>)) with the same output as <var class="Arg">bbox</var>, in the sense of <code class="func">AsBBoxProgram</code> (<a href="chap6.html#X826ACFE887E0B6B8"><span class="RefLink">6.2-5</span></a>), if such a straight line decision exists, and <code class="keyw">fail</code> otherwise.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">lines:= [ [ "Order", 1, 2 ], [ "Order", 2, 3 ],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [ [ 1, 1, 2, 1 ], 3 ], [ "Order", 3, 5 ] ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">dec:= StraightLineDecision( lines, 2 );</span>
<straight line decision>
<span class="GAPprompt">gap></span> <span class="GAPinput">bboxdec:= AsBBoxProgram( dec );</span>
<black box program>
<span class="GAPprompt">gap></span> <span class="GAPinput">asdec:= AsStraightLineDecision( bboxdec );</span>
<straight line decision>
<span class="GAPprompt">gap></span> <span class="GAPinput">LinesOfStraightLineDecision( asdec );</span>
[ [ "Order", 1, 2 ], [ "Order", 2, 3 ], [ [ 1, 1, 2, 1 ], 3 ],
[ "Order", 3, 5 ] ]
</pre></div>
<p><a id="X7EA613C57DDC67D5" name="X7EA613C57DDC67D5"></a></p>
<h5>6.1-9 StraightLineProgramFromStraightLineDecision</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ StraightLineProgramFromStraightLineDecision</code>( <var class="Arg">dec</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: the straight line program associated to the given straight line decision.</p>
<p>For a straight line decision <var class="Arg">dec</var> (see <code class="func">IsStraightLineDecision</code> (<a href="chap6.html#X8787E2EC7DB85A89"><span class="RefLink">6.1-1</span></a>), <code class="func">StraightLineProgramFromStraightLineDecision</code> returns the straight line program (see <code class="func">IsStraightLineProgram</code> (<a href="../../../doc/ref/chap37.html#X7F69FF3F7C6694CB"><span class="RefLink">Reference: IsStraightLineProgram</span></a>) obtained by replacing each line of type 3. (i.e, each order check) by an assignment of the power in question to a new slot, and by declaring the list of these elements as the return value.</p>
<p>This means that the return value describes exactly the defining relators of the presentation that is associated to the straight line decision, see <a href="chap6.html#X7C94ECAC8583CEAE"><span class="RefLink">6.1-7</span></a>.</p>
<p>For example, one can use the return value for printing the relators with <code class="func">StringOfResultOfStraightLineProgram</code> (<a href="../../../doc/ref/chap37.html#X8098EAAF7D344466"><span class="RefLink">Reference: StringOfResultOfStraightLineProgram</span></a>), or for explicitly constructing the relators as words in terms of free generators, by applying <code class="func">ResultOfStraightLineProgram</code> (<a href="../../../doc/ref/chap37.html#X7847D32B863E822F"><span class="RefLink">Reference: ResultOfStraightLineProgram</span></a>) to the program and to these generators.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">dec:= StraightLineDecision( [ [ [ 1, 1, 2, 1 ], 3 ],</span>
<span class="GAPprompt">></span> <span class="GAPinput">[ "Order", 1, 2 ], [ "Order", 2, 3 ], [ "Order", 3, 5 ] ] );</span>
<straight line decision>
<span class="GAPprompt">gap></span> <span class="GAPinput">prog:= StraightLineProgramFromStraightLineDecision( dec );</span>
<straight line program>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display( prog );</span>
# input:
r:= [ g1, g2 ];
# program:
r[3]:= r[1]*r[2];
r[4]:= r[1]^2;
r[5]:= r[2]^3;
r[6]:= r[3]^5;
# return values:
[ r[4], r[5], r[6] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">StringOfResultOfStraightLineProgram( prog, [ "a", "b" ] );</span>
"[ a^2, b^3, (ab)^5 ]"
<span class="GAPprompt">gap></span> <span class="GAPinput">gens:= GeneratorsOfGroup( FreeGroup( "a", "b" ) );</span>
[ a, b ]
<span class="GAPprompt">gap></span> <span class="GAPinput">ResultOfStraightLineProgram( prog, gens );</span>
[ a^2, b^3, (a*b)^5 ]
</pre></div>
<p><a id="X7BE856BC785A9E8F" name="X7BE856BC785A9E8F"></a></p>
<h4>6.2 <span class="Heading">Black Box Programs</span></h4>
<p><em>Black box programs</em> formalize the idea that one takes some group elements, forms arithmetic expressions in terms of them, tests properties of these expressions, executes conditional statements (including jumps inside the program) depending on the results of these tests, and eventually returns some result.</p>
<p>A specification of the language can be found in <a href="chapBib.html#biBNic06">[Nic06]</a>, see also</p>
<p><span class="URL"><a href="http://atlas.math.rwth-aachen.de/Atlas/info/blackbox.html">http://atlas.math.rwth-aachen.de/Atlas/info/blackbox.html</a></span>.</p>
<p>The <em>inputs</em> of a black box program may be explicit group elements, and the program may also ask for random elements from a given group. The <em>program steps</em> form products, inverses, conjugates, commutators, etc. of known elements, <em>tests</em> concern essentially the orders of elements, and the <em>result</em> is a list of group elements or <code class="keyw">true</code> or <code class="keyw">false</code> or <code class="keyw">fail</code>.</p>
<p>Examples that can be modeled by black box programs are</p>
<dl>
<dt><strong class="Mark"><em>straight line programs</em>,</strong></dt>
<dd><p>which require a fixed number of input elements and form arithmetic expressions of elements but do not use random elements, tests, conditional statements and jumps; the return value is always a list of elements; these programs are described in Section <a href="../../../doc/ref/chap37.html#X7DC99E4284093FBB"><span class="RefLink">Reference: Straight Line Programs</span></a>.</p>
</dd>
<dt><strong class="Mark"><em>straight line decisions</em>,</strong></dt>
<dd><p>which differ from straight line programs only in the sense that also order tests are admissible, and that the return value is <code class="keyw">true</code> if all these tests are satisfied, and <code class="keyw">false</code> as soon as the first such test fails; they are described in Section <a href="chap6.html#X8121E9567A7137C9"><span class="RefLink">6.1</span></a>.</p>
</dd>
<dt><strong class="Mark"><em>scripts for finding standard generators</em>,</strong></dt>
<dd><p>which take a group and a function to generate a random element in this group but no explicit input elements, admit all control structures, and return either a list of standard generators or <code class="keyw">fail</code>; see <code class="func">ResultOfBBoxProgram</code> (<a href="chap6.html#X869BACFB80A3CC87"><span class="RefLink">6.2-4</span></a>) for examples.</p>
</dd>
</dl>
<p>In the case of general black box programs, currently <strong class="pkg">GAP</strong> provides only the possibility to read an existing program via <code class="func">ScanBBoxProgram</code> (<a href="chap6.html#X7EA20532868F9863"><span class="RefLink">6.2-2</span></a>), and to run the program using <code class="func">RunBBoxProgram</code> (<a href="chap6.html#X7D211A5D8602B330"><span class="RefLink">6.2-3</span></a>). It is not our aim to write such programs in <strong class="pkg">GAP</strong>.</p>
<p>The special case of the <q>find</q> scripts mentioned above is also admissible as an argument of <code class="func">ResultOfBBoxProgram</code> (<a href="chap6.html#X869BACFB80A3CC87"><span class="RefLink">6.2-4</span></a>), which returns either the set of found generators or <code class="keyw">fail</code>.</p>
<p>Contrary to the general situation, more support is provided for straight line programs and straight line decisions in <strong class="pkg">GAP</strong>, see Section <a href="../../../doc/ref/chap37.html#X7DC99E4284093FBB"><span class="RefLink">Reference: Straight Line Programs</span></a> for functions that manipulate them (compose, restrict etc.).</p>
<p>The functions <code class="func">AsStraightLineProgram</code> (<a href="chap6.html#X7D36DFA87C8B2C48"><span class="RefLink">6.2-6</span></a>) and <code class="func">AsStraightLineDecision</code> (<a href="chap6.html#X7C13D08C7D55E20A"><span class="RefLink">6.1-8</span></a>) can be used to transform a general black box program object into a straight line program or a straight line decision if this is possible.</p>
<p>Conversely, one can create an equivalent general black box program from a straight line program or from a straight line decision with <code class="func">AsBBoxProgram</code> (<a href="chap6.html#X826ACFE887E0B6B8"><span class="RefLink">6.2-5</span></a>).</p>
<p>Computing a straight line program related to a given straight line decision is supported in the sense of <code class="func">StraightLineProgramFromStraightLineDecision</code> (<a href="chap6.html#X7EA613C57DDC67D5"><span class="RefLink">6.1-9</span></a>).</p>
<p>Note that none of these three kinds of objects is a special case of another: Running a black box program with <code class="func">RunBBoxProgram</code> (<a href="chap6.html#X7D211A5D8602B330"><span class="RefLink">6.2-3</span></a>) yields a record, running a straight line program with <code class="func">ResultOfStraightLineProgram</code> (<a href="../../../doc/ref/chap37.html#X7847D32B863E822F"><span class="RefLink">Reference: ResultOfStraightLineProgram</span></a>) yields a list of elements, and running a straight line decision with <code class="func">ResultOfStraightLineDecision</code> (<a href="chap6.html#X7E7B328A84685480"><span class="RefLink">6.1-6</span></a>) yields <code class="keyw">true</code> or <code class="keyw">false</code>.</p>
<p><a id="X87CAF2DE870D0E3B" name="X87CAF2DE870D0E3B"></a></p>
<h5>6.2-1 IsBBoxProgram</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsBBoxProgram</code>( <var class="Arg">obj</var> )</td><td class="tdright">( category )</td></tr></table></div>
<p>Each black box program in <strong class="pkg">GAP</strong> lies in the filter <code class="func">IsBBoxProgram</code>.</p>
<p><a id="X7EA20532868F9863" name="X7EA20532868F9863"></a></p>
<h5>6.2-2 ScanBBoxProgram</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ScanBBoxProgram</code>( <var class="Arg">string</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a record containing the black box program encoded by the input string, or <code class="keyw">fail</code>.</p>
<p>For a string <var class="Arg">string</var> that describes a black box program, e.g., the return value of <code class="func">StringFile</code> (<a href="../../../pkg/gapdoc/doc/chap6.html#X7E14D32181FBC3C3"><span class="RefLink">GAPDoc: StringFile</span></a>), <code class="func">ScanBBoxProgram</code> computes this black box program. If this is successful then the return value is a record containing as the value of its component <code class="code">program</code> the corresponding <strong class="pkg">GAP</strong> object that represents the program, otherwise <code class="keyw">fail</code> is returned.</p>
<p>As the first example, we construct a black box program that tries to find standard generators for the alternating group <span class="SimpleMath">A_5</span>; these standard generators are any pair of elements of the orders <span class="SimpleMath">2</span> and <span class="SimpleMath">3</span>, respectively, such that their product has order <span class="SimpleMath">5</span>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">findstr:= "\</span>
<span class="GAPprompt">></span> <span class="GAPinput"> set V 0\n\</span>
<span class="GAPprompt">></span> <span class="GAPinput">lbl START1\n\</span>
<span class="GAPprompt">></span> <span class="GAPinput"> rand 1\n\</span>
<span class="GAPprompt">></span> <span class="GAPinput"> ord 1 A\n\</span>
<span class="GAPprompt">></span> <span class="GAPinput"> incr V\n\</span>
<span class="GAPprompt">></span> <span class="GAPinput"> if V gt 100 then timeout\n\</span>
<span class="GAPprompt">></span> <span class="GAPinput"> if A notin 1 2 3 5 then fail\n\</span>
<span class="GAPprompt">></span> <span class="GAPinput"> if A noteq 2 then jmp START1\n\</span>
<span class="GAPprompt">></span> <span class="GAPinput">lbl START2\n\</span>
<span class="GAPprompt">></span> <span class="GAPinput"> rand 2\n\</span>
<span class="GAPprompt">></span> <span class="GAPinput"> ord 2 B\n\</span>
<span class="GAPprompt">></span> <span class="GAPinput"> incr V\n\</span>
<span class="GAPprompt">></span> <span class="GAPinput"> if V gt 100 then timeout\n\</span>
<span class="GAPprompt">></span> <span class="GAPinput"> if B notin 1 2 3 5 then fail\n\</span>
<span class="GAPprompt">></span> <span class="GAPinput"> if B noteq 3 then jmp START2\n\</span>
<span class="GAPprompt">></span> <span class="GAPinput"> # The elements 1 and 2 have the orders 2 and 3, respectively.\n\</span>
<span class="GAPprompt">></span> <span class="GAPinput"> set X 0\n\</span>
<span class="GAPprompt">></span> <span class="GAPinput">lbl CONJ\n\</span>
<span class="GAPprompt">></span> <span class="GAPinput"> incr X\n\</span>
<span class="GAPprompt">></span> <span class="GAPinput"> if X gt 100 then timeout\n\</span>
<span class="GAPprompt">></span> <span class="GAPinput"> rand 3\n\</span>
<span class="GAPprompt">></span> <span class="GAPinput"> cjr 2 3\n\</span>
<span class="GAPprompt">></span> <span class="GAPinput"> mu 1 2 4 # ab\n\</span>
<span class="GAPprompt">></span> <span class="GAPinput"> ord 4 C\n\</span>
<span class="GAPprompt">></span> <span class="GAPinput"> if C notin 2 3 5 then fail\n\</span>
<span class="GAPprompt">></span> <span class="GAPinput"> if C noteq 5 then jmp CONJ\n\</span>
<span class="GAPprompt">></span> <span class="GAPinput"> oup 2 1 2";;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">find:= ScanBBoxProgram( findstr );</span>
rec( program := <black box program> )
</pre></div>
<p>The second example is a black box program that checks whether its two inputs are standard generators for <span class="SimpleMath">A_5</span>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">checkstr:= "\</span>
<span class="GAPprompt">></span> <span class="GAPinput">chor 1 2\n\</span>
<span class="GAPprompt">></span> <span class="GAPinput">chor 2 3\n\</span>
<span class="GAPprompt">></span> <span class="GAPinput">mu 1 2 3\n\</span>
<span class="GAPprompt">></span> <span class="GAPinput">chor 3 5";;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">check:= ScanBBoxProgram( checkstr );</span>
rec( program := <black box program> )
</pre></div>
<p><a id="X7D211A5D8602B330" name="X7D211A5D8602B330"></a></p>
<h5>6.2-3 RunBBoxProgram</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RunBBoxProgram</code>( <var class="Arg">prog</var>, <var class="Arg">G</var>, <var class="Arg">input</var>, <var class="Arg">options</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a record describing the result and the statistics of running the black box program <var class="Arg">prog</var>, or <code class="keyw">fail</code>, or the string <code class="code">"timeout"</code>.</p>
<p>For a black box program <var class="Arg">prog</var>, a group <var class="Arg">G</var>, a list <var class="Arg">input</var> of group elements, and a record <var class="Arg">options</var>, <code class="func">RunBBoxProgram</code> applies <var class="Arg">prog</var> to <var class="Arg">input</var>, where <var class="Arg">G</var> is used only to compute random elements.</p>
<p>The return value is <code class="keyw">fail</code> if a syntax error or an explicit <code class="code">fail</code> statement is reached at runtime, and the string <code class="code">"timeout"</code> if a <code class="code">timeout</code> statement is reached. (The latter might mean that the random choices were unlucky.) Otherwise a record with the following components is returned.</p>
<dl>
<dt><strong class="Mark"><code class="code">gens</code></strong></dt>
<dd><p>a list of group elements, bound if an <code class="code">oup</code> statement was reached,</p>
</dd>
<dt><strong class="Mark"><code class="code">result</code></strong></dt>
<dd><p><code class="keyw">true</code> if a <code class="code">true</code> statement was reached, <code class="keyw">false</code> if either a <code class="code">false</code> statement or a failed order check was reached,</p>
</dd>
</dl>
<p>The other components serve as statistical information about the numbers of the various operations (<code class="code">multiply</code>, <code class="code">invert</code>, <code class="code">power</code>, <code class="code">order</code>, <code class="code">random</code>, <code class="code">conjugate</code>, <code class="code">conjugateinplace</code>, <code class="code">commutator</code>), and the runtime in milliseconds (<code class="code">timetaken</code>).</p>
<p>The following components of <var class="Arg">options</var> are supported.</p>
<dl>
<dt><strong class="Mark"><code class="code">randomfunction</code></strong></dt>
<dd><p>the function called with argument <var class="Arg">G</var> in order to compute a random element of <var class="Arg">G</var> (default <code class="func">PseudoRandom</code> (<a href="../../../doc/ref/chap30.html#X811B5BD47DC5356B"><span class="RefLink">Reference: PseudoRandom</span></a>))</p>
</dd>
<dt><strong class="Mark"><code class="code">orderfunction</code></strong></dt>
<dd><p>the function for computing element orders (default <code class="func">Order</code> (<a href="../../../doc/ref/chap31.html#X84F59A2687C62763"><span class="RefLink">Reference: Order</span></a>)),</p>
</dd>
<dt><strong class="Mark"><code class="code">quiet</code></strong></dt>
<dd><p>if <code class="keyw">true</code> then ignore <code class="code">echo</code> statements (default <code class="keyw">false</code>),</p>
</dd>
<dt><strong class="Mark"><code class="code">verbose</code></strong></dt>
<dd><p>if <code class="keyw">true</code> then print information about the line that is currently processed, and about order checks (default <code class="keyw">false</code>),</p>
</dd>
<dt><strong class="Mark"><code class="code">allowbreaks</code></strong></dt>
<dd><p>if <code class="keyw">true</code> then call <code class="func">Error</code> (<a href="../../../doc/ref/chap6.html#X7E7AD8D87EBA1A08"><span class="RefLink">Reference: Error</span></a>) when a <code class="code">break</code> statement is reached, otherwise ignore <code class="code">break</code> statements (default <code class="keyw">true</code>).</p>
</dd>
</dl>
<p>As an example, we run the black box programs constructed in the example for <code class="func">ScanBBoxProgram</code> (<a href="chap6.html#X7EA20532868F9863"><span class="RefLink">6.2-2</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">g:= AlternatingGroup( 5 );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">res:= RunBBoxProgram( find.program, g, [], rec() );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsBound( res.gens ); IsBound( res.result );</span>
true
false
<span class="GAPprompt">gap></span> <span class="GAPinput">List( res.gens, Order );</span>
[ 2, 3 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Order( Product( res.gens ) );</span>
5
<span class="GAPprompt">gap></span> <span class="GAPinput">res:= RunBBoxProgram( check.program, "dummy", res.gens, rec() );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsBound( res.gens ); IsBound( res.result );</span>
false
true
<span class="GAPprompt">gap></span> <span class="GAPinput">res.result;</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">othergens:= GeneratorsOfGroup( g );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">res:= RunBBoxProgram( check.program, "dummy", othergens, rec() );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">res.result;</span>
false
</pre></div>
<p><a id="X869BACFB80A3CC87" name="X869BACFB80A3CC87"></a></p>
<h5>6.2-4 ResultOfBBoxProgram</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ResultOfBBoxProgram</code>( <var class="Arg">prog</var>, <var class="Arg">G</var>[, <var class="Arg">options</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a list of group elements or <code class="keyw">true</code>, <code class="keyw">false</code>, <code class="keyw">fail</code>, or the string <code class="code">"timeout"</code>.</p>
<p>This function calls <code class="func">RunBBoxProgram</code> (<a href="chap6.html#X7D211A5D8602B330"><span class="RefLink">6.2-3</span></a>) with the black box program <var class="Arg">prog</var> and second argument either a group or a list of group elements; if <var class="Arg">options</var> is not given then the default options of <code class="func">RunBBoxProgram</code> (<a href="chap6.html#X7D211A5D8602B330"><span class="RefLink">6.2-3</span></a>) are assumed. The return value is <code class="keyw">fail</code> if this call yields <code class="keyw">fail</code>, otherwise the <code class="code">gens</code> component of the result, if bound, or the <code class="code">result</code> component if not.</p>
<p>Note that a <em>group</em> <var class="Arg">G</var> is used as the second argument in the call of <code class="func">RunBBoxProgram</code> (<a href="chap6.html#X7D211A5D8602B330"><span class="RefLink">6.2-3</span></a>) (the source for random elements), whereas a <em>list</em> <var class="Arg">G</var> is used as the third argument (the inputs).</p>
<p>As an example, we run the black box programs constructed in the example for <code class="func">ScanBBoxProgram</code> (<a href="chap6.html#X7EA20532868F9863"><span class="RefLink">6.2-2</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">g:= AlternatingGroup( 5 );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">res:= ResultOfBBoxProgram( find.program, g );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">List( res, Order );</span>
[ 2, 3 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Order( Product( res ) );</span>
5
<span class="GAPprompt">gap></span> <span class="GAPinput">res:= ResultOfBBoxProgram( check.program, res );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">othergens:= GeneratorsOfGroup( g );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">res:= ResultOfBBoxProgram( check.program, othergens );</span>
false
</pre></div>
<p><a id="X826ACFE887E0B6B8" name="X826ACFE887E0B6B8"></a></p>
<h5>6.2-5 AsBBoxProgram</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AsBBoxProgram</code>( <var class="Arg">slp</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: an equivalent black box program for the given straight line program or straight line decision.</p>
<p>Let <var class="Arg">slp</var> be a straight line program (see <code class="func">IsStraightLineProgram</code> (<a href="../../../doc/ref/chap37.html#X7F69FF3F7C6694CB"><span class="RefLink">Reference: IsStraightLineProgram</span></a>)) or a straight line decision (see <code class="func">IsStraightLineDecision</code> (<a href="chap6.html#X8787E2EC7DB85A89"><span class="RefLink">6.1-1</span></a>)). Then <code class="func">AsBBoxProgram</code> returns a black box program <var class="Arg">bbox</var> (see <code class="func">IsBBoxProgram</code> (<a href="chap6.html#X87CAF2DE870D0E3B"><span class="RefLink">6.2-1</span></a>)) with the <q>same</q> output as <var class="Arg">slp</var>, in the sense that <code class="func">ResultOfBBoxProgram</code> (<a href="chap6.html#X869BACFB80A3CC87"><span class="RefLink">6.2-4</span></a>) yields the same result for <var class="Arg">bbox</var> as <code class="func">ResultOfStraightLineProgram</code> (<a href="../../../doc/ref/chap37.html#X7847D32B863E822F"><span class="RefLink">Reference: ResultOfStraightLineProgram</span></a>) or <code class="func">ResultOfStraightLineDecision</code> (<a href="chap6.html#X7E7B328A84685480"><span class="RefLink">6.1-6</span></a>), respectively, for <var class="Arg">slp</var>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">f:= FreeGroup( "x", "y" );; gens:= GeneratorsOfGroup( f );;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">slp:= StraightLineProgram( [ [1,2,2,3], [3,-1] ], 2 );</span>
<straight line program>
<span class="GAPprompt">gap></span> <span class="GAPinput">ResultOfStraightLineProgram( slp, gens );</span>
y^-3*x^-2
<span class="GAPprompt">gap></span> <span class="GAPinput">bboxslp:= AsBBoxProgram( slp );</span>
<black box program>
<span class="GAPprompt">gap></span> <span class="GAPinput">ResultOfBBoxProgram( bboxslp, gens );</span>
[ y^-3*x^-2 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">lines:= [ [ "Order", 1, 2 ], [ "Order", 2, 3 ],</span>
<span class="GAPprompt">></span> <span class="GAPinput"> [ [ 1, 1, 2, 1 ], 3 ], [ "Order", 3, 5 ] ];;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">dec:= StraightLineDecision( lines, 2 );</span>
<straight line decision>
<span class="GAPprompt">gap></span> <span class="GAPinput">ResultOfStraightLineDecision( dec, [ (1,2)(3,4), (1,3,5) ] );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">ResultOfStraightLineDecision( dec, [ (1,2)(3,4), (1,3,4) ] );</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">bboxdec:= AsBBoxProgram( dec );</span>
<black box program>
<span class="GAPprompt">gap></span> <span class="GAPinput">ResultOfBBoxProgram( bboxdec, [ (1,2)(3,4), (1,3,5) ] );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">ResultOfBBoxProgram( bboxdec, [ (1,2)(3,4), (1,3,4) ] );</span>
false
</pre></div>
<p><a id="X7D36DFA87C8B2C48" name="X7D36DFA87C8B2C48"></a></p>
<h5>6.2-6 AsStraightLineProgram</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AsStraightLineProgram</code>( <var class="Arg">bbox</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>Returns: an equivalent straight line program for the given black box program, or <code class="keyw">fail</code>.</p>
<p>For a black box program (see <code class="func">AsBBoxProgram</code> (<a href="chap6.html#X826ACFE887E0B6B8"><span class="RefLink">6.2-5</span></a>)) <var class="Arg">bbox</var>, <code class="func">AsStraightLineProgram</code> returns a straight line program (see <code class="func">IsStraightLineProgram</code> (<a href="../../../doc/ref/chap37.html#X7F69FF3F7C6694CB"><span class="RefLink">Reference: IsStraightLineProgram</span></a>)) with the same output as <var class="Arg">bbox</var> if such a straight line program exists, and <code class="keyw">fail</code> otherwise.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display( AsStraightLineProgram( bboxslp ) );</span>
# input:
r:= [ g1, g2 ];
# program:
r[3]:= r[1]^2;
r[4]:= r[2]^3;
r[5]:= r[3]*r[4];
r[3]:= r[5]^-1;
# return values:
[ r[3] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">AsStraightLineProgram( bboxdec );</span>
fail
</pre></div>
<p><a id="X87E1F08D80C9E069" name="X87E1F08D80C9E069"></a></p>
<h4>6.3 <span class="Heading">Representations of Minimal Degree</span></h4>
<p>This section deals with minimal degrees of permutation and matrix representations. We do not provide an algorithm that computes these degrees for an arbitrary group, we only provide some tools for evaluating known databases, mainly concerning <q>bicyclic extensions</q> (see <a href="chapBib.html#biBCCN85">[CCN+85, Section 6.5]</a>) of simple groups, in order to derive the minimal degrees, see Section <a href="chap6.html#X7FC33DFF8481F8D1"><span class="RefLink">6.3-4</span></a>.</p>
<p>In the <strong class="pkg">AtlasRep</strong> package, this information can be used for prescribing <q>minimality conditions</q> in <code class="func">DisplayAtlasInfo</code> (<a href="chap3.html#X79DACFFA7E2D1A99"><span class="RefLink">3.5-1</span></a>), <code class="func">OneAtlasGeneratingSetInfo</code> (<a href="chap3.html#X841478AB7CD06D44"><span class="RefLink">3.5-6</span></a>), and <code class="func">AllAtlasGeneratingSetInfos</code> (<a href="chap3.html#X84C2D76482E60E42"><span class="RefLink">3.5-7</span></a>). An overview of the stored minimal degrees can be shown with <code class="func">BrowseMinimalDegrees</code> (<a href="chap3.html#X7F31A7CB841FE63F"><span class="RefLink">3.6-1</span></a>).</p>
<p><a id="X7DC66D8282B2BB7F" name="X7DC66D8282B2BB7F"></a></p>
<h5>6.3-1 MinimalRepresentationInfo</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MinimalRepresentationInfo</code>( <var class="Arg">grpname</var>, <var class="Arg">conditions</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a record with the components <code class="code">value</code> and <code class="code">source</code>, or <code class="keyw">fail</code></p>
<p>Let <var class="Arg">grpname</var> be the <strong class="pkg">GAP</strong> name of a group <span class="SimpleMath">G</span>, say. If the information described by <var class="Arg">conditions</var> about minimal representations of this group can be computed or is stored then <code class="func">MinimalRepresentationInfo</code> returns a record with the components <code class="code">value</code> and <code class="code">source</code>, otherwise <code class="keyw">fail</code> is returned.</p>
<p>The following values for <var class="Arg">conditions</var> are supported.</p>
<ul>
<li><p>If <var class="Arg">conditions</var> is <code class="func">NrMovedPoints</code> (<a href="../../../doc/ref/chap42.html#X85E7B1E28430F49E"><span class="RefLink">Reference: NrMovedPoints for a permutation</span></a>) then <code class="code">value</code>, if known, is the degree of a minimal faithful (not necessarily transitive) permutation representation for <span class="SimpleMath">G</span>.</p>
</li>
<li><p>If <var class="Arg">conditions</var> consists of <code class="func">Characteristic</code> (<a href="../../../doc/ref/chap31.html#X81278E53800BF64D"><span class="RefLink">Reference: Characteristic</span></a>) and a prime integer <var class="Arg">p</var> then <code class="code">value</code>, if known, is the dimension of a minimal faithful (not necessarily irreducible) matrix representation in characteristic <var class="Arg">p</var> for <span class="SimpleMath">G</span>.</p>
</li>
<li><p>If <var class="Arg">conditions</var> consists of <code class="func">Size</code> (<a href="../../../doc/ref/chap30.html#X858ADA3B7A684421"><span class="RefLink">Reference: Size</span></a>) and a prime power <var class="Arg">q</var> then <code class="code">value</code>, if known, is the dimension of a minimal faithful (not necessarily irreducible) matrix representation over the field of size <var class="Arg">q</var> for <span class="SimpleMath">G</span>.</p>
</li>
</ul>
<p>In all cases, the value of the component <code class="code">source</code> is a list of strings that describe sources of the information, which can be the ordinary or modular character table of <span class="SimpleMath">G</span> (see <a href="chapBib.html#biBCCN85">[CCN+85]</a>, <a href="chapBib.html#biBJLPW95">[JLPW95]</a>, <a href="chapBib.html#biBHL89">[HL89]</a>), the table of marks of <span class="SimpleMath">G</span>, or <a href="chapBib.html#biBJan05">[Jan05]</a>. For an overview of minimal degrees of faithful matrix representations for sporadic simple groups and their covering groups, see also</p>
<p><span class="URL"><a href="http://www.math.rwth-aachen.de/~MOC/mindeg/">http://www.math.rwth-aachen.de/~MOC/mindeg/</a></span>.</p>
<p>Note that <code class="func">MinimalRepresentationInfo</code> cannot provide any information about minimal representations over prescribed fields in characteristic zero.</p>
<p>Information about groups that occur in the <strong class="pkg">AtlasRep</strong> package is precomputed in <code class="func">MinimalRepresentationInfoData</code> (<a href="chap6.html#X7E1B76DC86A8C405"><span class="RefLink">6.3-2</span></a>), so the packages <strong class="pkg">CTblLib</strong> and <strong class="pkg">TomLib</strong> are not needed when <code class="func">MinimalRepresentationInfo</code> is called for these groups. (The only case that is not covered by this list is that one asks for the minimal degree of matrix representations over a prescribed field in characteristic coprime to the group order.)</p>
<p>One of the following strings can be given as an additional last argument.</p>
<dl>
<dt><strong class="Mark"><code class="code">"cache"</code></strong></dt>
<dd><p>means that the function tries to compute (and then store) values that are not stored in <code class="func">MinimalRepresentationInfoData</code> (<a href="chap6.html#X7E1B76DC86A8C405"><span class="RefLink">6.3-2</span></a>), but stored values are preferred; this is also the default.</p>
</dd>
<dt><strong class="Mark"><code class="code">"lookup"</code></strong></dt>
<dd><p>means that stored values are returned but the function does not attempt to compute values that are not stored in <code class="func">MinimalRepresentationInfoData</code> (<a href="chap6.html#X7E1B76DC86A8C405"><span class="RefLink">6.3-2</span></a>).</p>
</dd>
<dt><strong class="Mark"><code class="code">"recompute"</code></strong></dt>
<dd><p>means that the function always tries to compute the desired value, and checks the result against stored values.</p>
</dd>
</dl>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">MinimalRepresentationInfo( "A5", NrMovedPoints );</span>
rec(
source := [ "computed (alternating group)",
"computed (char. table)", "computed (subgroup tables)",
"computed (subgroup tables, known repres.)",
"computed (table of marks)" ], value := 5 )
<span class="GAPprompt">gap></span> <span class="GAPinput">MinimalRepresentationInfo( "A5", Characteristic, 2 );</span>
rec( source := [ "computed (char. table)" ], value := 2 )
<span class="GAPprompt">gap></span> <span class="GAPinput">MinimalRepresentationInfo( "A5", Size, 2 );</span>
rec( source := [ "computed (char. table)" ], value := 4 )
</pre></div>
<p><a id="X7E1B76DC86A8C405" name="X7E1B76DC86A8C405"></a></p>
<h5>6.3-2 MinimalRepresentationInfoData</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MinimalRepresentationInfoData</code></td><td class="tdright">( global variable )</td></tr></table></div>
<p>This is a record whose components are <strong class="pkg">GAP</strong> names of groups for which information about minimal permutation and matrix representations were known in advance or have been computed in the current <strong class="pkg">GAP</strong> session. The value for the group <span class="SimpleMath">G</span>, say, is a record with the following components.</p>
<dl>
<dt><strong class="Mark"><code class="code">NrMovedPoints</code></strong></dt>
<dd><p>a record with the components <code class="code">value</code> (the degree of a smallest faithful permutation representation of <span class="SimpleMath">G</span>) and <code class="code">source</code> (a string describing the source of this information).</p>
</dd>
<dt><strong class="Mark"><code class="code">Characteristic</code></strong></dt>
<dd><p>a record whose components are at most <code class="code">0</code> and strings corresponding to prime integers, each bound to a record with the components <code class="code">value</code> (the degree of a smallest faithful matrix representation of <span class="SimpleMath">G</span> in this characteristic) and <code class="code">source</code> (a string describing the source of this information).</p>
</dd>
<dt><strong class="Mark"><code class="code">CharacteristicAndSize</code></strong></dt>
<dd><p>a record whose components are strings corresponding to prime integers <var class="Arg">p</var>, each bound to a record with the components <code class="code">sizes</code> (a list of powers <var class="Arg">q</var> of <var class="Arg">p</var>), <code class="code">dimensions</code> (the corresponding list of minimal dimensions of faithful matrix representations of <span class="SimpleMath">G</span> over a field of size <var class="Arg">q</var>), <code class="code">sources</code> (the corresponding list of strings describing the source of this information), and <code class="code">complete</code> (a record with the components <code class="code">val</code> (<code class="keyw">true</code> if the minimal dimension over <em>any</em> finite field in characteristic <var class="Arg">p</var> can be derived from the values in the record, and <code class="keyw">false</code> otherwise) and <code class="code">source</code> (a string describing the source of this information)).</p>
</dd>
</dl>
<p>The values are set by <code class="func">SetMinimalRepresentationInfo</code> (<a href="chap6.html#X79C4C9F683E919C9"><span class="RefLink">6.3-3</span></a>).</p>
<p><a id="X79C4C9F683E919C9" name="X79C4C9F683E919C9"></a></p>
<h5>6.3-3 SetMinimalRepresentationInfo</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SetMinimalRepresentationInfo</code>( <var class="Arg">grpname</var>, <var class="Arg">op</var>, <var class="Arg">value</var>, <var class="Arg">source</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: <code class="keyw">true</code> if the values were successfully set, <code class="keyw">false</code> if stored values contradict the given ones.</p>
<p>This function sets an entry in <code class="func">MinimalRepresentationInfoData</code> (<a href="chap6.html#X7E1B76DC86A8C405"><span class="RefLink">6.3-2</span></a>) for the group <span class="SimpleMath">G</span>, say, with <strong class="pkg">GAP</strong> name <var class="Arg">grpname</var>.</p>
<p>Supported values for <var class="Arg">op</var> are</p>
<ul>
<li><p><code class="code">"NrMovedPoints"</code> (see <code class="func">NrMovedPoints</code> (<a href="../../../doc/ref/chap42.html#X85E7B1E28430F49E"><span class="RefLink">Reference: NrMovedPoints for a permutation</span></a>)), which means that <var class="Arg">value</var> is the degree of minimal faithful (not necessarily transitive) permutation representations of <span class="SimpleMath">G</span>,</p>
</li>
<li><p>a list of length two with first entry <code class="code">"Characteristic"</code> (see <code class="func">Characteristic</code> (<a href="../../../doc/ref/chap31.html#X81278E53800BF64D"><span class="RefLink">Reference: Characteristic</span></a>)) and second entry <var class="Arg">char</var> either zero or a prime integer, which means that <var class="Arg">value</var> is the dimension of minimal faithful (not necessarily irreducible) matrix representations of <span class="SimpleMath">G</span> in characteristic <var class="Arg">char</var>,</p>
</li>
<li><p>a list of length two with first entry <code class="code">"Size"</code> (see <code class="func">Size</code> (<a href="../../../doc/ref/chap30.html#X858ADA3B7A684421"><span class="RefLink">Reference: Size</span></a>)) and second entry a prime power <var class="Arg">q</var>, which means that <var class="Arg">value</var> is the dimension of minimal faithful (not necessarily irreducible) matrix representations of <span class="SimpleMath">G</span> over the field with <var class="Arg">q</var> elements, and</p>
</li>
<li><p>a list of length three with first entry <code class="code">"Characteristic"</code> (see <code class="func">Characteristic</code> (<a href="../../../doc/ref/chap31.html#X81278E53800BF64D"><span class="RefLink">Reference: Characteristic</span></a>)), second entry a prime integer <var class="Arg">p</var>, and third entry the string <code class="code">"complete"</code>, which means that the information stored for characteristic <var class="Arg">p</var> is complete in the sense that for any given power <span class="SimpleMath">q</span> of <var class="Arg">p</var>, the minimal faithful degree over the field with <span class="SimpleMath">q</span> elements equals that for the largest stored field size of which <span class="SimpleMath">q</span> is a power.</p>
</li>
</ul>
<p>In each case, <var class="Arg">source</var> is a string describing the source of the data; <em>computed</em> values are detected from the prefix <code class="code">"comp"</code> of <var class="Arg">source</var>.</p>
<p>If the intended value is already stored and differs from <var class="Arg">value</var> then an error message is printed.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">SetMinimalRepresentationInfo( "A5", "NrMovedPoints", 5,</span>
<span class="GAPprompt">></span> <span class="GAPinput"> "computed (alternating group)" );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">SetMinimalRepresentationInfo( "A5", [ "Characteristic", 0 ], 3,</span>
<span class="GAPprompt">></span> <span class="GAPinput"> "computed (char. table)" );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">SetMinimalRepresentationInfo( "A5", [ "Characteristic", 2 ], 2,</span>
<span class="GAPprompt">></span> <span class="GAPinput"> "computed (char. table)" );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">SetMinimalRepresentationInfo( "A5", [ "Size", 2 ], 4,</span>
<span class="GAPprompt">></span> <span class="GAPinput"> "computed (char. table)" );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">SetMinimalRepresentationInfo( "A5", [ "Size", 4 ], 2,</span>
<span class="GAPprompt">></span> <span class="GAPinput"> "computed (char. table)" );</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">SetMinimalRepresentationInfo( "A5", [ "Characteristic", 3 ], 3,</span>
<span class="GAPprompt">></span> <span class="GAPinput"> "computed (char. table)" );</span>
true
</pre></div>
<p><a id="X7FC33DFF8481F8D1" name="X7FC33DFF8481F8D1"></a></p>
<h5>6.3-4 <span class="Heading">Criteria Used to Compute Minimality Information</span></h5>
<p>The information about the minimal degree of a faithful <em>matrix representation</em> of <span class="SimpleMath">G</span> in a given characteristic or over a given field in positive characteristic is derived from the relevant (ordinary or modular) character table of <span class="SimpleMath">G</span>, except in a few cases where this table itself is not known but enough information about the degrees is available in <a href="chapBib.html#biBHL89">[HL89]</a> and <a href="chapBib.html#biBJan05">[Jan05]</a>.</p>
<p>The following criteria are used for deriving the minimal degree of a faithful <em>permutation representation</em> of <span class="SimpleMath">G</span> from the information in the <strong class="pkg">GAP</strong> libraries of character tables and of tables of marks.</p>
<ul>
<li><p>If the name of <span class="SimpleMath">G</span> has the form <code class="code">"A</code><span class="SimpleMath">n</span><code class="code">"</code> or <code class="code">"A</code><span class="SimpleMath">n</span><code class="code">.2"</code> (denoting alternating and symmetric groups, respectively) then the minimal degree is <span class="SimpleMath">n</span>, except if <span class="SimpleMath">n</span> is smaller than <span class="SimpleMath">3</span> or <span class="SimpleMath">2</span>, respectively.</p>
</li>
<li><p>If the name of <span class="SimpleMath">G</span> has the form <code class="code">"L2(</code><span class="SimpleMath">q</span><code class="code">)"</code> (denoting projective special linear groups in dimension two) then the minimal degree is <span class="SimpleMath">q + 1</span>, except if <span class="SimpleMath">q ∈ { 2, 3, 5, 7, 9, 11 }</span>, see <a href="chapBib.html#biBHup67">[Hup67, Satz II.8.28]</a>.</p>
</li>
<li><p>If the largest maximal subgroup of <span class="SimpleMath">G</span> is core-free then the index of this subgroup is the minimal degree. (This is used when the two character tables in question and the class fusion are available in <strong class="pkg">GAP</strong>'s Character Table Library <a href="chapBib.html#biBCTblLib">[Bre22]</a>; this happens for many character tables of simple groups.)</p>
</li>
<li><p>If <span class="SimpleMath">G</span> has a unique minimal normal subgroup then each minimal faithful permutation representation is transitive. (Note that the core of each point stabilizer is either trivial or contains the unique minimal normal subgroup.)</p>
<p>In this case, the minimal degree can be computed directly from the information in the table of marks of <span class="SimpleMath">G</span> if this is available in <strong class="pkg">GAP</strong>'s Library of Tables of Marks <a href="chapBib.html#biBTomLib">[NMP18]</a>.</p>
<p>Suppose that the largest maximal subgroup of <span class="SimpleMath">G</span> is not core-free but simple and normal in <span class="SimpleMath">G</span>, and that the other maximal subgroups of <span class="SimpleMath">G</span> are core-free. In this case, we take the minimum of the indices of the core-free maximal subgroups and of the product of index and minimal degree of the normal maximal subgroup. (This suffices since no core-free subgroup of the whole group can contain a nontrivial normal subgroup of a normal maximal subgroup.)</p>
<p>Let <span class="SimpleMath">N</span> be the unique minimal normal subgroup of <span class="SimpleMath">G</span>, and assume that <span class="SimpleMath">G/N</span> is simple and has minimal degree <span class="SimpleMath">n</span>, say. If there is a subgroup <span class="SimpleMath">U</span> of index <span class="SimpleMath">n ⋅ |N|</span> in <span class="SimpleMath">G</span> that intersects <span class="SimpleMath">N</span> trivially then the minimal degree of <span class="SimpleMath">G</span> is <span class="SimpleMath">n ⋅ |N|</span>. (This is used for the case that <span class="SimpleMath">N</span> is central in <span class="SimpleMath">G</span> and <span class="SimpleMath">N × U</span> occurs as a subgroup of <span class="SimpleMath">G</span>.)</p>
</li>
<li><p>If we know a subgroup of <span class="SimpleMath">G</span> whose minimal degree is <span class="SimpleMath">n</span>, say, and if we know either (a class fusion from) a core-free subgroup of index <span class="SimpleMath">n</span> in <span class="SimpleMath">G</span> or a faithful permutation representation of degree <span class="SimpleMath">n</span> for <span class="SimpleMath">G</span> then <span class="SimpleMath">n</span> is the minimal degree for <span class="SimpleMath">G</span>. (This happens often for tables of almost simple groups.)</p>
</li>
</ul>
<p><a id="X7E5CB1637F127B2E" name="X7E5CB1637F127B2E"></a></p>
<h4>6.4 <span class="Heading">A JSON Interface</span></h4>
<p>We define a mapping between certain <strong class="pkg">GAP</strong> objects and JSON (JavaScript Object Notation) texts (see <a href="chapBib.html#biBJSON">[JSO14]</a>), as follows.</p>
<ul>
<li><p>The three <strong class="pkg">GAP</strong> values <code class="keyw">true</code>, <code class="keyw">false</code>, and <code class="keyw">fail</code> correspond to the JSON texts <code class="code">true</code>, <code class="code">false</code>, and <code class="code">null</code>, respectively.</p>
</li>
<li><p><strong class="pkg">GAP</strong> strings correspond to JSON strings; special characters in a <strong class="pkg">GAP</strong> string (control characters ASCII <span class="SimpleMath">0</span> to <span class="SimpleMath">31</span>, backslash and double quote) are mapped as defined in JSON's specification, and other ASCII characters are kept as they are; if a <strong class="pkg">GAP</strong> string contains non-ASCII characters, it is assumed that it is UTF-8 encoded, and one may choose either to keep non-ASCII characters as they are, or to create an ASCII only JSON string, using JSON's syntax for Unicode code points (<q><code class="code">\uXXXX</code></q>); in the other direction, JSON strings are assumed to be UTF-8 encoded, and are mapped to UTF-8 encoded <strong class="pkg">GAP</strong> strings, by keeping the non-ASCII characters and converting substrings of the form <code class="code">\uXXXX</code> accordingly.</p>
</li>
<li><p><strong class="pkg">GAP</strong> integers (in the sense of <code class="func">IsInt</code> (<a href="../../../doc/ref/chap14.html#X87AEADF07DC8303B"><span class="RefLink">Reference: IsInt</span></a>)) are mapped to JSON numbers that consist of digits and optionally a leading sign character <code class="code">-</code>; in the other direction, JSON numbers of this form and also JSON numbers that involve no decimal dots and have no negative exponent (for example <code class="code">"2e3"</code>) are mapped to <strong class="pkg">GAP</strong> integers.</p>
</li>
<li><p><strong class="pkg">GAP</strong> rationals (in the sense of <code class="func">IsRat</code> (<a href="../../../doc/ref/chap17.html#X7ED018F5794935F7"><span class="RefLink">Reference: IsRat</span></a>)) which are not integers are represented by JSON floating point numbers; the JSON representation (and hence the precision) is given by first applying <code class="func">Float</code> (<a href="../../../doc/ref/chap19.html#X86D5EA93813FB6C4"><span class="RefLink">Reference: Float</span></a>) and then <code class="func">String</code> (<a href="../../../doc/ref/chap27.html#X81FB5BE27903EC32"><span class="RefLink">Reference: String</span></a>).</p>
</li>
<li><p><strong class="pkg">GAP</strong> floats (in the sense of Chapter <a href="../../../doc/ref/chap19.html#X81AA901181CA568F"><span class="RefLink">Reference: Floats</span></a> in the <strong class="pkg">GAP</strong> Reference Manual) are mapped to JSON floating point numbers; the JSON representation (and hence the precision) is given by applying <code class="func">String</code> (<a href="../../../doc/ref/chap27.html#X81FB5BE27903EC32"><span class="RefLink">Reference: String</span></a>); in the other direction, JSON numbers that involve a decimal dot or a negative exponent are mapped to <strong class="pkg">GAP</strong> floats.</p>
</li>
<li><p>(Nested and not self-referential) dense <strong class="pkg">GAP</strong> lists of objects correspond to JSON arrays such that the list entries correspond to each other. (Note that JSON does not support non-dense arrays.)</p>
</li>
<li><p>(Nested and not self-referential) <strong class="pkg">GAP</strong> records correspond to JSON objects such that both labels (which are strings in <strong class="pkg">GAP</strong> and JSON) and values correspond to each other.</p>
</li>
</ul>
<p>The <strong class="pkg">GAP</strong> functions <code class="func">AGR.JsonText</code> (<a href="chap6.html#X87A307D284975AA9"><span class="RefLink">6.4-2</span></a>) and <code class="func">AGR.GapObjectOfJsonText</code> (<a href="chap6.html#X79DF4DC67DCFE27B"><span class="RefLink">6.4-3</span></a>) can be used to create a JSON text from a suitable <strong class="pkg">GAP</strong> object and the <strong class="pkg">GAP</strong> object that corresponds to a given JSON text, respectively.</p>
<p>Note that the composition of the two functions is in general <em>not</em> the identity mapping, because <code class="func">AGR.JsonText</code> (<a href="chap6.html#X87A307D284975AA9"><span class="RefLink">6.4-2</span></a>) accepts non-integer rationals, whereas <code class="func">AGR.GapObjectOfJsonText</code> (<a href="chap6.html#X79DF4DC67DCFE27B"><span class="RefLink">6.4-3</span></a>) does not create such objects.</p>
<p>Note also that the results of <code class="func">AGR.JsonText</code> (<a href="chap6.html#X87A307D284975AA9"><span class="RefLink">6.4-2</span></a>) do not contain information about dependencies between common subobjects. This is another reason why applying first <code class="func">AGR.JsonText</code> (<a href="chap6.html#X87A307D284975AA9"><span class="RefLink">6.4-2</span></a>) and then <code class="func">AGR.GapObjectOfJsonText</code> (<a href="chap6.html#X79DF4DC67DCFE27B"><span class="RefLink">6.4-3</span></a>) may yield a <strong class="pkg">GAP</strong> object with different behaviour.</p>
<p>Applying <code class="func">AGR.JsonText</code> (<a href="chap6.html#X87A307D284975AA9"><span class="RefLink">6.4-2</span></a>) to a self-referential object such as <code class="code">[ ~ ]</code> will raise a <q>recursion depth trap</q> error.</p>
<p><a id="X7870BBB184574D18" name="X7870BBB184574D18"></a></p>
<h5>6.4-1 <span class="Heading">Why JSON?</span></h5>
<p>The aim of this JSON interface is to read and write certain data files with <strong class="pkg">GAP</strong> such that these files become easily accessible independent of <strong class="pkg">GAP</strong>. The function <code class="func">AGR.JsonText</code> (<a href="chap6.html#X87A307D284975AA9"><span class="RefLink">6.4-2</span></a>) is intended just as a prototype, variants of this function are very likely to appear in other contexts, for example in order to force certain line formatting or ordering of record components.</p>
<p>It is <em>not</em> the aim of the JSON interface to provide self-contained descriptions of arbitrary <strong class="pkg">GAP</strong> objects, in order to read them into a <strong class="pkg">GAP</strong> session. Note that those <strong class="pkg">GAP</strong> objects for which a JSON equivalent exists (and many more) can be easily written to files as they are, and <strong class="pkg">GAP</strong> can read them efficiently. On the other hand, more complicated <strong class="pkg">GAP</strong> objects can be written and read via the so-called <em>pickling</em>, for which a framework is provided by the <strong class="pkg">GAP</strong> package <strong class="pkg">IO</strong> <a href="chapBib.html#biBIO">[Neu14]</a>.</p>
<p>Here are a few situations which are handled well by pickling but which cannot be addressed with a JSON interface.</p>
<ul>
<li><p>Pickling and unpickling take care of common subobjects of the given <strong class="pkg">GAP</strong> object. The following example shows that the applying first <code class="func">AGR.JsonText</code> (<a href="chap6.html#X87A307D284975AA9"><span class="RefLink">6.4-2</span></a>) and then <code class="func">AGR.GapObjectOfJsonText</code> (<a href="chap6.html#X79DF4DC67DCFE27B"><span class="RefLink">6.4-3</span></a>) may yield an object which behaves differently.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">l:= [ [ 1 ] ];; l[2]:= l[1];; l;</span>
[ [ 1 ], [ 1 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">new:= AGR.GapObjectOfJsonText( AGR.JsonText( l ) ).value;</span>
[ [ 1 ], [ 1 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Add( l[1], 2 ); l;</span>
[ [ 1, 2 ], [ 1, 2 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Add( new[1], 2 ); new;</span>
[ [ 1, 2 ], [ 1 ] ]
</pre></div>
</li>
<li><p><strong class="pkg">GAP</strong> admits self-referential objects, for example as follows.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">l:= [];; l[1]:= l;;</span>
</pre></div>
<p>Pickling and unpickling take care of self-referential objects, but <code class="func">AGR.JsonText</code> (<a href="chap6.html#X87A307D284975AA9"><span class="RefLink">6.4-2</span></a>) does not support the conversion of such objects.</p>
</li>
</ul>
<p><a id="X87A307D284975AA9" name="X87A307D284975AA9"></a></p>
<h5>6.4-2 AGR.JsonText</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AGR.JsonText</code>( <var class="Arg">obj</var>[, <var class="Arg">mode</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a new mutable string that describes <var class="Arg">obj</var> as a JSON text, or <code class="keyw">fail</code>.</p>
<p>If <var class="Arg">obj</var> is a <strong class="pkg">GAP</strong> object for which a corresponding JSON text exists, according to the mapping described above, then such a JSON text is returned. Otherwise, <code class="keyw">fail</code> is returned.</p>
<p>If the optional argument <var class="Arg">mode</var> is given and has the value <code class="code">"ASCII"</code> then the result in an ASCII string, otherwise the encoding of strings that are involved in <var class="Arg">obj</var> is kept.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">AGR.JsonText( [] );</span>
"[]"
<span class="GAPprompt">gap></span> <span class="GAPinput">AGR.JsonText( "" );</span>
"\"\""
<span class="GAPprompt">gap></span> <span class="GAPinput">AGR.JsonText( "abc\ndef\cghi" );</span>
"\"abc\\ndef\\u0003ghi\""
<span class="GAPprompt">gap></span> <span class="GAPinput">AGR.JsonText( rec() );</span>
"{}"
<span class="GAPprompt">gap></span> <span class="GAPinput">AGR.JsonText( [ , 2 ] );</span>
fail
<span class="GAPprompt">gap></span> <span class="GAPinput">str:= [ '\303', '\266' ];; # umlaut o</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">json:= AGR.JsonText( str );; List( json, IntChar );</span>
[ 34, 195, 182, 34 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">AGR.JsonText( str, "ASCII" );</span>
"\"\\u00F6\""
</pre></div>
<p><a id="X79DF4DC67DCFE27B" name="X79DF4DC67DCFE27B"></a></p>
<h5>6.4-3 AGR.GapObjectOfJsonText</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AGR.GapObjectOfJsonText</code>( <var class="Arg">string</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: a new mutable record whose <code class="code">value</code> component, if bound, contains a mutable <strong class="pkg">GAP</strong> object that represents the JSON text <var class="Arg">string</var>.</p>
<p>If <var class="Arg">string</var> is a string that represents a JSON text then the result is a record with the components <code class="code">value</code> (the corresponding <strong class="pkg">GAP</strong> object in the sense of the above interface) and <code class="code">status</code> (value <code class="keyw">true</code>). Otherwise, the result is a record with the components <code class="code">status</code> (value <code class="keyw">false</code>) and <code class="code">errpos</code> (the position in <var class="Arg">string</var> where the string turns out to be not valid JSON).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">AGR.GapObjectOfJsonText( "{ \"a\": 1 }" );</span>
rec( status := true, value := rec( a := 1 ) )
<span class="GAPprompt">gap></span> <span class="GAPinput">AGR.GapObjectOfJsonText( "{ \"a\": x }" );</span>
rec( errpos := 8, status := false )
</pre></div>
<div class="chlinkprevnextbot"> <a href="chap0.html">[Top of Book]</a> <a href="chap0.html#contents">[Contents]</a> <a href="chap5.html">[Previous Chapter]</a> <a href="chap7.html">[Next Chapter]</a> </div>
<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chap7.html">7</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<hr />
<p class="foot">generated by <a href="https://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>
|
