This file is indexed.

/usr/share/gap/doc/tut/chap5.html is in gap-doc 4r7p9-1.

This file is owned by root:root, with mode 0o644.

The actual contents of the file can be viewed below.

  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
<?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 (tut) - Chapter 5: Groups and Homomorphisms</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="chap5"  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="chap8.html">8</a>  <a href="chapBib.html">Bib</a>  <a href="chapInd.html">Ind</a>  </div>

<div class="chlinkprevnexttop">&nbsp;<a href="chap0.html">[Top of Book]</a>&nbsp;  <a href="chap0.html#contents">[Contents]</a>&nbsp;  &nbsp;<a href="chap4.html">[Previous Chapter]</a>&nbsp;  &nbsp;<a href="chap6.html">[Next Chapter]</a>&nbsp;  </div>

<p id="mathjaxlink" class="pcenter"><a href="chap5_mj.html">[MathJax on]</a></p>
<p><a id="X8171DAF2833FF728" name="X8171DAF2833FF728"></a></p>
<div class="ChapSects"><a href="chap5.html#X8171DAF2833FF728">5 <span class="Heading">Groups and Homomorphisms</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap5.html#X85ED46007CED6191">5.1 <span class="Heading">Permutation groups</span></a>
</span>
</div>
<div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap5.html#X8493BB7D7ECB5AB2">5.2 <span class="Heading">Actions of Groups</span></a>
</span>
</div>
<div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap5.html#X8742F6A083ADE513">5.3 <span class="Heading">Subgroups as Stabilizers</span></a>
</span>
</div>
<div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap5.html#X8131EE9182385680">5.4 <span class="Heading">Group Homomorphisms by Images</span></a>
</span>
</div>
<div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap5.html#X7FFD731684606BC6">5.5 <span class="Heading">Nice Monomorphisms</span></a>
</span>
</div>
<div class="ContSect"><span class="tocline"><span class="nocss">&nbsp;</span><a href="chap5.html#X84579FB48474079C">5.6 <span class="Heading">Further Information about Groups and Homomorphisms</span></a>
</span>
</div>
</div>

<h3>5 <span class="Heading">Groups and Homomorphisms</span></h3>

<p>In this chapter we will show some computations with groups. The examples deal mostly with permutation groups, because they are the easiest to input. The functions mentioned here, like <code class="func">Group</code> (<a href="../../doc/ref/chap39.html#X8716635F7951801B"><span class="RefLink">Reference: Groups</span></a>), <code class="func">Size</code> (<a href="../../doc/ref/chap30.html#X858ADA3B7A684421"><span class="RefLink">Reference: Size</span></a>) or <code class="func">SylowSubgroup</code> (<a href="../../doc/ref/chap39.html#X7AA351308787544C"><span class="RefLink">Reference: SylowSubgroup</span></a>), however, are the same for all kinds of groups, although the algorithms which compute the information of course will be different in most cases.</p>

<p><a id="X85ED46007CED6191" name="X85ED46007CED6191"></a></p>

<h4>5.1 <span class="Heading">Permutation groups</span></h4>

<p>Permutation groups are so easy to input because their elements, i.e., permutations, are so easy to type: they are entered and displayed in disjoint cycle notation. So let's construct a permutation group:</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">s8 := Group( (1,2), (1,2,3,4,5,6,7,8) );</span>
Group([ (1,2), (1,2,3,4,5,6,7,8) ])
</pre></div>

<p>We formed the group generated by the permutations <code class="code">(1,2)</code> and <code class="code">(1,2,3,4,5,6,7,8)</code>, which is well known to be the symmetric group <span class="SimpleMath">S_8</span> on eight points, and assigned it to the identifier <code class="code">s8</code>. Now <span class="SimpleMath">S_8</span> contains the alternating group on eight points which can be described in several ways, e.g., as the group of all even permutations in <code class="code">s8</code>, or as its derived subgroup. Once we ask <strong class="pkg">GAP</strong> to verify that the group is an alternating group acting in its natural permutation representation, the system will display the group accordingly.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">a8 := DerivedSubgroup( s8 );</span>
Group([ (1,2,3), (2,3,4), (2,4)(3,5), (2,6,4), (2,4)(5,7), 
  (2,8,6,4)(3,5) ])
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Size( a8 ); IsAbelian( a8 ); IsPerfect( a8 );</span>
20160
false
true
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">IsNaturalAlternatingGroup(a8);</span>
true
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">a8;</span>
Alt( [ 1 .. 8 ] )
</pre></div>

<p>Once information about a group like <code class="code">s8</code> or <code class="code">a8</code> has been computed, it is stored in the group so that it can simply be looked up when it is required again. This holds for all pieces of information in the previous example. Namely, <code class="code">a8</code> stores its order and that it is nonabelian and perfect, and <code class="code">s8</code> stores its derived subgroup <code class="code">a8</code>. Had we computed <code class="code">a8</code> as <code class="code">CommutatorSubgroup( s8, s8 )</code>, however, it would not have been stored, because it would then have been computed as a function of <em>two</em> arguments, and hence one could not attribute it to just one of them. (Of course the function <code class="func">CommutatorSubgroup</code> (<a href="../../doc/ref/chap39.html#X7A9A3D5578CE33A0"><span class="RefLink">Reference: CommutatorSubgroup</span></a>) can compute the commutator subgroup of <em>two</em> arbitrary subgroups.) The situation is a bit different for Sylow <span class="SimpleMath">p</span>-subgroups: The function <code class="func">SylowSubgroup</code> (<a href="../../doc/ref/chap39.html#X7AA351308787544C"><span class="RefLink">Reference: SylowSubgroup</span></a>) also requires two arguments, namely a group and a prime <span class="SimpleMath">p</span>, but the result is stored in the group –namely together with the prime <span class="SimpleMath">p</span> in a list that can be accessed with <code class="code">ComputedSylowSubgroups</code>, but we won't dwell on the details here.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">syl2 := SylowSubgroup( a8, 2 );; Size( syl2 );</span>
64
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Normalizer( a8, syl2 ) = syl2;</span>
true
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">cent := Centralizer( a8, Centre( syl2 ) );; Size( cent );</span>
192
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">DerivedSeries( cent );; List( last, Size );</span>
[ 192, 96, 32, 2, 1 ]
</pre></div>

<p>We have typed double semicolons after some commands to avoid the output of the groups (which would be printed by their generator lists). Nevertheless, the beginner is encouraged to type a single semicolon instead and study the full output. This remark also applies for the rest of this tutorial.</p>

<p>With the next examples, we want to calculate a subgroup of <code class="code">a8</code>, then its normalizer and finally determine the structure of the extension. We begin by forming a subgroup generated by three commuting involutions, i.e., a subgroup isomorphic to the additive group of the vector space <span class="SimpleMath">2^3</span>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">elab := Group( (1,2)(3,4)(5,6)(7,8), (1,3)(2,4)(5,7)(6,8),</span>
<span class="GAPprompt">&gt;</span> <span class="GAPinput">                  (1,5)(2,6)(3,7)(4,8) );;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Size( elab );</span>
8
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">IsElementaryAbelian( elab );</span>
true
</pre></div>

<p>As usual, <strong class="pkg">GAP</strong> prints the group by giving all its generators. This can be annoying, especially if there are many of them or if they are of huge degree. It also makes it difficult to recognize a particular group when there are already several around. Note that although it is no problem for <em>us</em> to specify a particular group to <strong class="pkg">GAP</strong>, by using well-chosen identifiers such as <code class="code">a8</code> and <code class="code">elab</code>, it is impossible for <strong class="pkg">GAP</strong> to use these identifiers when printing a group for us, because the group does not know which identifier(s) point to it, in fact there can be several. In order to give a name to the group itself (rather than to the identifier), you can use the function <code class="func">SetName</code> (<a href="../../doc/ref/chap12.html#X85D6D47B83BD02A1"><span class="RefLink">Reference: SetName</span></a>). We do this with the name <code class="code">2^3</code> here which reflects the mathematical properties of the group. From now on, <strong class="pkg">GAP</strong> will use this name when printing the group for us, but we still cannot use this name to specify the group to <strong class="pkg">GAP</strong>, because the name does not know to which group it was assigned (after all, you could assign the same name to several groups). When talking to the computer, you must always use identifiers.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">SetName( elab, "&lt;group of type 2^3&gt;" ); elab;</span>
&lt;group of type 2^3&gt;
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">norm := Normalizer( a8, elab );; Size( norm );</span>
1344
</pre></div>

<p>Now that we have the subgroup <code class="code">norm</code> of order 1344 and its subgroup <code class="code">elab</code>, we want to look at its factor group. But since we also want to find preimages of factor group elements in <code class="code">norm</code>, we really want to look at the <em>natural homomorphism</em> defined on <code class="code">norm</code> with kernel <code class="code">elab</code> and whose image is the factor group.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">hom := NaturalHomomorphismByNormalSubgroup( norm, elab );</span>
&lt;action epimorphism&gt;
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">f := Image( hom );</span>
Group([ (), (), (), (4,5)(6,7), (4,6)(5,7), (2,3)(6,7), (2,4)(3,5), 
 (1,2)(5,6) ])
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Size( f );</span>
168
</pre></div>

<p>The factor group is again represented as a permutation group (its first three generators are trivial, meaning that the first three generators of the preimage are in the kernel of <code class="code">hom</code>). However, the action domain of this factor group has nothing to do with the action domain of <code class="code">norm</code>. (It only happens that both are subsets of the natural numbers.) We can now form images and preimages under the natural homomorphism. The set of preimages of an element under <code class="code">hom</code> is a coset modulo <code class="code">elab</code>. We use the function <code class="func">PreImages</code> (<a href="../../doc/ref/chap32.html#X85C8590E832002EF"><span class="RefLink">Reference: PreImages</span></a>) here because <code class="code">hom</code> is not a bijection, so an element of the range can have several preimages or none at all.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">ker:= Kernel( hom );</span>
&lt;group of type 2^3&gt;
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">x := (1,8,3,5,7,6,2);; Image( hom, x );</span>
(1,7,5,6,2,3,4)
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">coset := PreImages( hom, last );</span>
RightCoset(&lt;group of type 2^3&gt;,(2,8,6,7,3,4,5))
</pre></div>

<p>Note that <strong class="pkg">GAP</strong> is free to choose any representative for the coset of preimages. Of course the quotient of two representatives lies in the kernel of the homomorphism.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">rep:= Representative( coset );</span>
(2,8,6,7,3,4,5)
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">x * rep^-1 in ker;</span>
true
</pre></div>

<p>The factor group <code class="code">f</code> is a simple group, i.e., it has no non-trivial normal subgroups. <strong class="pkg">GAP</strong> can detect this fact, and it can then also find the name by which this simple group is known among group theorists. (Such names are of course not available for non-simple groups.)</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">IsSimple( f ); IsomorphismTypeInfoFiniteSimpleGroup( f );</span>
true
rec( 
  name := "A(1,7) = L(2,7) ~ B(1,7) = O(3,7) ~ C(1,7) = S(2,7) ~ 2A(1,\
7) = U(2,7) ~ A(2,2) = L(3,2)", parameter := [ 2, 7 ], series := "L" )
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">SetName( f, "L_3(2)" );</span>
</pre></div>

<p>We give <code class="code">f</code> the name <code class="code">L_3(2)</code> because the last part of the name string reveals that it is isomorphic to the simple linear group <span class="SimpleMath">L_3(2)</span>. This group, however, also has a lot of other names. Names that are connected with a <code class="code">=</code> sign are different names for the same matrix group, e.g., <code class="code">A(2,2)</code> is the Lie type notation for the classical notation <code class="code">L(3,2)</code>. Other pairs of names are connected via <code class="code">~</code>, these then specify other classical groups that are isomorphic to that linear group (e.g., the symplectic group <code class="code">S(2,7)</code>, whose Lie type notation would be <code class="code">C(1,7)</code>).</p>

<p>The group <code class="code">norm</code> acts on the eight elements of its normal subgroup <code class="code">elab</code> by conjugation, yielding a representation of <span class="SimpleMath">L_3(2)</span> in <code class="code">s8</code> which leaves one point fixed (namely point <code class="code">1</code>). The image of this representation can be computed with the function <code class="func">Action</code> (<a href="../../doc/ref/chap40.html#X86C2BE2481FDC8EE"><span class="RefLink">Reference: Action homomorphisms</span></a>); it is even contained in the group <code class="code">norm</code> and we can show that <code class="code">norm</code> is indeed a split extension of the elementary abelian group <span class="SimpleMath">2^3</span> with this image of <span class="SimpleMath">L_3(2)</span>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">op := Action( norm, elab );</span>
Group([ (), (), (), (5,6)(7,8), (5,7)(6,8), (3,4)(7,8), (3,5)(4,6), 
  (2,3)(6,7) ])
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">IsSubgroup( a8, op ); IsSubgroup( norm, op );</span>
true
true
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">IsTrivial( Intersection( elab, op ) );</span>
true
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">SetName( norm, "2^3:L_3(2)" );</span>
</pre></div>

<p>By the way, you should not try the operator <code class="code">&lt;</code> instead of the function <code class="func">IsSubgroup</code> (<a href="../../doc/ref/chap39.html#X7839D8927E778334"><span class="RefLink">Reference: IsSubgroup</span></a>). Something like</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">elab &lt; a8;</span>
false
</pre></div>

<p>will not cause an error, but the result does not signify anything about the inclusion of one group in another; <code class="code">&lt;</code> tests which of the two groups is less in some total order. On the other hand, the equality operator <code class="code">=</code> in fact does test the equality of its arguments.</p>

<p><em>Summary.</em> In this section we have used the elementary group functions to determine the structure of a normalizer. We have assigned names to the involved groups which reflect their mathematical structure and <strong class="pkg">GAP</strong> uses these names when printing the groups.</p>

<p><a id="X8493BB7D7ECB5AB2" name="X8493BB7D7ECB5AB2"></a></p>

<h4>5.2 <span class="Heading">Actions of Groups</span></h4>

<p>In order to get another representation of <code class="code">a8</code>, we consider another action, namely that on the elements of a certain conjugacy class by conjugation.</p>

<p>In the following example we temporarily increase the line length limit from its default value 80 to 82 in order to make the long expression fit into one line.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">ccl := ConjugacyClasses( a8 );; Length( ccl );</span>
14
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">List( ccl, c -&gt; Order( Representative( c ) ) );</span>
[ 1, 2, 2, 3, 6, 3, 4, 4, 5, 15, 15, 6, 7, 7 ]
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">List( ccl, Size );</span>
[ 1, 210, 105, 112, 1680, 1120, 2520, 1260, 1344, 1344, 1344, 3360, 
  2880, 2880 ]
</pre></div>

<p>Note the difference between <code class="func">Order</code> (<a href="../../doc/ref/chap31.html#X84F59A2687C62763"><span class="RefLink">Reference: Order</span></a>) (which means the element order), <code class="func">Size</code> (<a href="../../doc/ref/chap30.html#X858ADA3B7A684421"><span class="RefLink">Reference: Size</span></a>) (which means the size of the conjugacy class) and <code class="func">Length</code> (<a href="../../doc/ref/chap21.html#X780769238600AFD1"><span class="RefLink">Reference: Length</span></a>) (which means the length of a list). We choose to let <code class="code">a8</code> operate on the class of length 112.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">class := First( ccl, c -&gt; Size(c) = 112 );;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">op := Action( a8, AsList( class ),OnPoints );;</span>
</pre></div>

<p>We use <code class="func">AsList</code> (<a href="../../doc/ref/chap30.html#X8289FCCC8274C89D"><span class="RefLink">Reference: AsList</span></a>) here to convert the conjugacy class into a list of its elements whereas we wrote <code class="code">Action( norm, elab )</code> directly in the previous section. The reason is that the elementary abelian group <code class="code">elab</code> can be quickly enumerated by <strong class="pkg">GAP</strong> whereas the standard enumeration method for conjugacy classes is slower than just explicit calculation of the elements. However, <strong class="pkg">GAP</strong> is reluctant to construct explicit element lists, because for really large groups this direct method is infeasible.</p>

<p>Note also the function <code class="func">First</code> (<a href="../../doc/ref/chap21.html#X82801DFA84E11272"><span class="RefLink">Reference: First</span></a>), used to find the first element in a list which passes some test.</p>

<p>In this example, we have specified the action function <code class="func">OnPoints</code> (<a href="../../doc/ref/chap41.html#X7FE417DD837987B4"><span class="RefLink">Reference: OnPoints</span></a>) in this example, which is defined as <code class="code">OnPoints( </code><span class="SimpleMath">d</span><code class="code">, </code><span class="SimpleMath">g</span><code class="code"> ) = </code><span class="SimpleMath">d</span><code class="code"> ^ </code><span class="SimpleMath">g</span>. This "caret" operator denotes conjugation in a group if both arguments <span class="SimpleMath">d</span> and <span class="SimpleMath">g</span> are group elements (contained in a common group), but it also denotes the natural action of permutations on positive integers (and exponentiation of integers as well, of course). It is in fact the default action and will be supplied by the system if not given. Another common action is for example always assumes <code class="func">OnRight</code> (<a href="../../doc/ref/chap41.html#X7960924D84B5B18F"><span class="RefLink">Reference: OnRight</span></a>), which means right multiplication, defined as <span class="SimpleMath">d</span><code class="code"> * </code><span class="SimpleMath">g</span>. (Group actions in <strong class="pkg">GAP</strong> are always from the right.)</p>

<p>We now have a permutation representation <code class="code">op</code> on 112 points, which we test for primitivity. If it is not primitive, we can obtain a minimal block system (i.e., one where the blocks have minimal length) by the function <code class="func">Blocks</code> (<a href="../../doc/ref/chap41.html#X84FE699F85371643"><span class="RefLink">Reference: Blocks</span></a>).</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">IsPrimitive( op, [ 1 .. 112 ] );</span>
false
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">blocks := Blocks( op, [ 1 .. 112 ] );;</span>
</pre></div>

<p>Note that we must specify the domain of the action. You might think that the functions <code class="func">IsPrimitive</code> (<a href="../../doc/ref/chap41.html#X84C19AD68247B760"><span class="RefLink">Reference: IsPrimitive</span></a>) and <code class="func">Blocks</code> (<a href="../../doc/ref/chap41.html#X84FE699F85371643"><span class="RefLink">Reference: Blocks</span></a>) could use <code class="code">[ 1 .. 112 ]</code> as default domain if no domain was given. But this is not so easy, for example would the default domain of <code class="code">Group( (2,3,4) )</code> be <code class="code">[ 1 .. 4 ]</code> or <code class="code">[ 2 .. 4 ]</code>? To avoid confusion, all action functions require that you specify the domain of action. If we had specified <code class="code">[ 1 .. 113 ]</code> in the primitivity test above, point 113 would have been a fixpoint (and the action would not even have been transitive).</p>

<p>Now <code class="code">blocks</code> is a list of blocks (i.e., a list of lists), which we do not print here for the sake of saving paper (try it for yourself). In fact all we want to know is the size of the blocks, or rather how many there are (the product of these two numbers must of course be 112). Then we can obtain a new permutation group of the corresponding degree by letting <code class="code">op</code> act on these blocks setwise.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Length( blocks[1] );  Length( blocks );</span>
2
56
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">op2 := Action( op, blocks, OnSets );;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">IsPrimitive( op2, [ 1 .. 56 ] );</span>
true
</pre></div>

<p>Note that we give a third argument (the action function <code class="func">OnSets</code> (<a href="../../doc/ref/chap41.html#X85AA04347CD117F9"><span class="RefLink">Reference: OnSets</span></a>)) to indicate that the action is not the default action on points but an action on sets of elements given as sorted lists. (Section <a href="../../doc/ref/chap41.html#X81B8F9CD868CD953"><span class="RefLink">Reference: Basic Actions</span></a> lists all actions that are pre-defined by <strong class="pkg">GAP</strong>.)</p>

<p>The action of <code class="code">op</code> on the given block system gave us a new representation on 56 points which is primitive, i.e., the point stabilizer is a maximal subgroup. We compute its preimage in the representation on eight points using the associated action homomorphisms (which of course in this case are monomorphisms). We construct the composition of two homomorphisms with the <code class="code">*</code> operator, reading left-to-right.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">ophom := ActionHomomorphism( a8, op );;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">ophom2 := ActionHomomorphism( op, op2 );;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">composition := ophom * ophom2;;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">stab := Stabilizer( op2, 2 );;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">preim := PreImages( composition, stab );</span>
Group([ (1,4,2), (3,6,7), (3,8,5,7,6), (1,4)(7,8) ])
</pre></div>

<p>Alternatively, it is possible to create action homomorphisms immediately (without creating the action first) by giving the same set of arguments to <code class="func">ActionHomomorphism</code> (<a href="../../doc/ref/chap41.html#X78E6A002835288A4"><span class="RefLink">Reference: ActionHomomorphism</span></a>).</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">nophom := ActionHomomorphism( a8, AsList(class) );</span>
&lt;action homomorphism&gt;
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">IsSurjective(nophom);</span>
false
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Image(nophom,(1,2,3));</span>
(2,43,14)(3,44,20)(4,45,26)(5,46,32)(6,47,38)(8,13,48)(9,19,53)(10,25,
58)(11,31,63)(12,37,68)(15,49,73)(16,50,74)(17,51,75)(18,52,76)(21,54,
77)(22,55,78)(23,56,79)(24,57,80)(27,59,81)(28,60,82)(29,61,83)(30,62,
84)(33,64,85)(34,65,86)(35,66,87)(36,67,88)(39,69,89)(40,70,90)(41,71,
91)(42,72,92)
</pre></div>

<p>In this situation, however (for performance reasons, avoiding computation an image that might never be needed) the homomorphism is defined to be not into the <em>Image</em> of the action, but into the <em>full symmetric group</em>, i.e. it is not automatically surjective. Surjectivity can be enforced by giving the string <code class="code">"surjective"</code> as an extra last argument. The <code class="code">Image</code> of the action homomorphism of course is the same group in either case.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Size(Range(nophom));</span>
1974506857221074023536820372759924883412778680349753377966562950949028\
5896977181144089422435502777936659795733823785363827233491968638562181\
1850780464277094400000000000000000000000000
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Size(Range(ophom));</span>
20160
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">nophom := ActionHomomorphism( a8, AsList(class),"surjective" );</span>
&lt;action epimorphism&gt;
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Size(Range(nophom));</span>
20160
</pre></div>

<p>Continuing the example, the normalizer of an element in the conjugacy class <code class="code">class</code> is a group of order 360, too. In fact, it is a conjugate of the maximal subgroup we had found before, and a conjugating element in <code class="code">a8</code> is found by the function <code class="func">RepresentativeAction</code> (<a href="../../doc/ref/chap41.html#X857DC7B085EB0539"><span class="RefLink">Reference: RepresentativeAction</span></a>).</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">sgp := Normalizer( a8, Subgroup(a8,[Representative(class)]) );;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Size( sgp );</span>
360
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">RepresentativeAction( a8, sgp, preim );</span>
(2,4,3)
</pre></div>

<p>One of the most prominent actions of a group is on the cosets of a subgroup. Naïvely this can be done by constructing the cosets and acting on them by right multiplication.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">cosets:=RightCosets(a8,norm);;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">op:=Action(a8,cosets,OnRight);</span>
Group([ (1,2,3)(4,6,5)(7,8,9)(10,12,11)(13,14,15), 
  (1,3,2)(4,9,13)(5,11,7)(6,15,10)(8,12,14), 
  (1,13)(2,7)(3,10)(4,11)(5,15)(6,9), 
  (1,8,13)(2,7,12)(3,9,5)(4,14,11)(6,10,15), 
  (2,3)(4,14)(5,7)(8,13)(9,12)(10,15), 
  (1,8)(2,3,11,6)(4,12,10,15)(5,7,14,9) ])
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">NrMovedPoints(op);</span>
15
</pre></div>

<p>A problem with this approach is that creating (and storing) all cosets can be very memory intensive if the subgroup index gets large. Because of this, <strong class="pkg">GAP</strong> provides special objects which act like a list of elements, but do not actually store elements but compute them on the go. Such a simulated list is called an <em>enumerator</em>. The easiest example of this concept is the <code class="func">Enumerator</code> (<a href="../../doc/ref/chap30.html#X7EF8910F82B45EC7"><span class="RefLink">Reference: Enumerator</span></a>) of a group. While it behaves like a list of elements, it requires far less storage, and is applicable to potentially huge groups for which it would be completely infeasible to write down all elements:</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">enum:=Enumerator(SymmetricGroup(20));</span>
&lt;enumerator of perm group&gt;
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Length(enum);</span>
2432902008176640000
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">enum[123456789012345];</span>
(1,4,15,3,14,11,8,17,6,18,5,7,20,13,10,9,2,12)
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Position(enum,(1,2,3,4,5,6,7,8,9,10));</span>
71948729603
</pre></div>

<p>For the action on cosets the object of interest is the <code class="func">RightTransversal</code> (<a href="../../doc/ref/chap39.html#X85C65D06822E716F"><span class="RefLink">Reference: RightTransversal</span></a>) of a subgroup. Again, it does not write out actual elements and thus can be created even for subgroups of large index.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">t:=RightTransversal(a8,norm);</span>
RightTransversal(Alt( [ 1 .. 8 ] ),2^3:L_3(2))
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">t[7];</span>
(4,6,5)
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Position(t,(4,6,7,8,5));</span>
8
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Position(t,(1,2,3));</span>
fail
</pre></div>

<p>For the action on cosets there is the added complication that not every group element is in the transversal (as the last example shows) but the action on cosets of a subgroup usually will not preserve a chosen set of coset representatives. Because of this issue, all action functionality actually uses <code class="func">PositionCanonical</code> (<a href="../../doc/ref/chap21.html#X7B4B10AE81602D4E"><span class="RefLink">Reference: PositionCanonical</span></a>) instead of <code class="func">Position</code> (<a href="../../doc/ref/chap21.html#X79975EC6783B4293"><span class="RefLink">Reference: Position</span></a>). In general, for elements contained in a list, <code class="func">PositionCanonical</code> (<a href="../../doc/ref/chap21.html#X7B4B10AE81602D4E"><span class="RefLink">Reference: PositionCanonical</span></a>) returns the same as <code class="code">Position</code>. If the element is not contained in the list (and for special lists, such as transversals), <code class="code">PositionCanonical</code> returns the list element representing the same objects, e.g. the transversal element representing the same coset.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">PositionCanonical(t,(1,2,3));</span>
2
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">t[2];</span>
(6,7,8)
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">t[2]/(1,2,3);</span>
(1,3,2)(6,7,8)
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">last in norm;</span>
true
</pre></div>

<p>Thus, acting on a <code class="code">RightTransversal</code> with the <code class="code">OnRight</code> action will in fact (in a slight abuse of definitions) produce the action of a group on cosets of a subgroup and is in general the most efficient way of creating this action.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Action(a8,RightTransversal(a8,norm),OnRight);</span>
Group([ (1,2,3)(4,6,5)(7,8,9)(10,12,11)(13,14,15), 
  (1,3,2)(4,9,13)(5,11,7)(6,15,10)(8,12,14), 
  (1,13)(2,7)(3,10)(4,11)(5,15)(6,9), 
  (1,8,13)(2,7,12)(3,9,5)(4,14,11)(6,10,15), 
  (2,3)(4,14)(5,7)(8,13)(9,12)(10,15), 
  (1,8)(2,3,11,6)(4,12,10,15)(5,7,14,9) ])
</pre></div>

<p><em>Summary.</em> In this section we have learned how groups can operate on <strong class="pkg">GAP</strong> objects such as integers and group elements. We have used <code class="func">ActionHomomorphism</code> (<a href="../../doc/ref/chap41.html#X78E6A002835288A4"><span class="RefLink">Reference: ActionHomomorphism</span></a>), among others, to construct the corresponding actions and homomorphisms and have seen how transversals can be used to create the action on cosets of a subgroup.</p>

<p><a id="X8742F6A083ADE513" name="X8742F6A083ADE513"></a></p>

<h4>5.3 <span class="Heading">Subgroups as Stabilizers</span></h4>

<p>Action functions can also be used without constructing external sets. We will try to find several subgroups in <code class="code">a8</code> as stabilizers of such actions. One subgroup is immediately available, namely the stabilizer of one point. The index of the stabilizer must of course be equal to the length of the orbit, i.e., 8.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">u8 := Stabilizer( a8, 1 );</span>
Group([ (2,3,4), (2,4)(3,5), (2,6,4), (2,4)(5,7), (2,8,6,4)(3,5) ])
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Index( a8, u8 );</span>
8
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Orbit( a8, 1 ); Length( last );</span>
[ 1, 3, 2, 4, 5, 6, 7, 8 ]
8
</pre></div>

<p>This gives us a hint how to find further subgroups. Each subgroup is the stabilizer of a point of an appropriate transitive action (namely the action on the cosets of that subgroup or another action that is equivalent to this action). So the question is how to find other actions. The obvious thing is to operate on pairs of points. So using the function <code class="func">Tuples</code> (<a href="../../doc/ref/chap16.html#X86A3CA0F7CC8C320"><span class="RefLink">Reference: Tuples</span></a>) we first generate a list of all pairs.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">pairs := Tuples( [1..8], 2 );;</span>
</pre></div>

<p>Now we would like to have <code class="code">a8</code> operate on this domain. But we cannot use the default action <code class="func">OnPoints</code> (<a href="../../doc/ref/chap41.html#X7FE417DD837987B4"><span class="RefLink">Reference: OnPoints</span></a>) because powering a list by a permutation via the caret operator <code class="code">^</code> is not defined. So we must tell the functions from the actions package how the group elements operate on the elements of the domain (here and below, the word "package" refers to the <strong class="pkg">GAP</strong> functionality for group actions, not to a <strong class="pkg">GAP</strong> package). In our example we can do this by simply passing <code class="func">OnPairs</code> (<a href="../../doc/ref/chap41.html#X80DAA1D2855B1456"><span class="RefLink">Reference: OnPairs</span></a>) as an optional last argument. All functions from the actions package accept such an optional argument that describes the action. One example is <code class="func">IsTransitive</code> (<a href="../../doc/ref/chap41.html#X79B15750851828CB"><span class="RefLink">Reference: IsTransitive</span></a>).</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">IsTransitive( a8, pairs, OnPairs );</span>
false
</pre></div>

<p>The action is of course not transitive, since the pairs <code class="code">[ 1, 1 ]</code> and <code class="code">[ 1, 2 ]</code> cannot lie in the same orbit. So we want to find out what the orbits are. The function <code class="func">Orbits</code> (<a href="../../doc/ref/chap41.html#X81E0FF0587C54543"><span class="RefLink">Reference: Orbits</span></a>) does that for us. It returns a list of all the orbits. We look at the orbit lengths and representatives for the orbits.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">orbs := Orbits( a8, pairs, OnPairs );; Length( orbs );</span>
2
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">List( orbs, Length );</span>
[ 8, 56 ]
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">List( orbs, o -&gt; o[1] );</span>
[ [ 1, 1 ], [ 1, 2 ] ]
</pre></div>

<p>The action of <code class="code">a8</code> on the first orbit (this is the one containing <code class="code">[1,1]</code>, try <code class="code">[1,1] in orbs[1]</code>) is of course equivalent to the original action, so we ignore it and work with the second orbit.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">u56 := Stabilizer( a8, orbs[2][1], OnPairs );; Index( a8, u56 );</span>
56
</pre></div>

<p>So now we have found a second subgroup. To make the following computations a little bit easier and more efficient we would now like to work on the points <code class="code">[ 1 .. 56 ]</code> instead of the list of pairs. The function <code class="func">ActionHomomorphism</code> (<a href="../../doc/ref/chap41.html#X78E6A002835288A4"><span class="RefLink">Reference: ActionHomomorphism</span></a>) does what we need. It creates a homomorphism defined on <code class="code">a8</code> whose image is a new group that acts on <code class="code">[ 1 .. 56 ]</code> in the same way that <code class="code">a8</code> acts on the second orbit.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">h56 := ActionHomomorphism( a8, orbs[2], OnPairs );;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">a8_56 := Image( h56 );;</span>
</pre></div>

<p>We would now like to know if the subgroup <code class="code">u56</code> of index 56 that we found is maximal or not. As we have used already in Section <a href="chap5.html#X8493BB7D7ECB5AB2"><span class="RefLink">5.2</span></a>, a subgroup is maximal if and only if the action on the cosets of this subgroup is primitive.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">IsPrimitive( a8_56, [1..56] );</span>
false
</pre></div>

<p>Remember that we can leave out the function if we mean <code class="func">OnPoints</code> (<a href="../../doc/ref/chap41.html#X7FE417DD837987B4"><span class="RefLink">Reference: OnPoints</span></a>) but that we have to specify the action domain for all action functions.</p>

<p>We see that <code class="code">a8_56</code> is not primitive. This means of course that the action of <code class="code">a8</code> on <code class="code">orb[2]</code> is not primitive, because those two actions are equivalent. So the stabilizer <code class="code">u56</code> is not maximal. Let us try to find its supergroups. We use the function <code class="func">Blocks</code> (<a href="../../doc/ref/chap41.html#X84FE699F85371643"><span class="RefLink">Reference: Blocks</span></a>) to find a block system. The (optional) third argument in the following example tells <code class="func">Blocks</code> (<a href="../../doc/ref/chap41.html#X84FE699F85371643"><span class="RefLink">Reference: Blocks</span></a>) that we want a block system where 1 and 3 lie in one block.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">blocks := Blocks( a8_56, [1..56], [1,3] );;</span>
</pre></div>

<p>The result is a list of sets, such that <code class="code">a8_56</code> acts on those sets. Now we would like the stabilizer of this action on the sets. Because we want to operate on the sets we have to pass <code class="func">OnSets</code> (<a href="../../doc/ref/chap41.html#X85AA04347CD117F9"><span class="RefLink">Reference: OnSets</span></a>) as third argument.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">u8_56 := Stabilizer( a8_56, blocks[1], OnSets );;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Index( a8_56, u8_56 );</span>
8
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">u8b := PreImages( h56, u8_56 );; Index( a8, u8b );</span>
8
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">IsConjugate( a8, u8, u8b );</span>
true
</pre></div>

<p>So we have found a supergroup of <code class="code">u56</code> that is conjugate in <code class="code">a8</code> to <code class="code">u8</code>. This is not surprising, since <code class="code">u8</code> is a point stabilizer, and <code class="code">u56</code> is a two point stabilizer in the natural action of <code class="code">a8</code> on eight points.</p>

<p>Here is a <em>warning</em>: If you specify <code class="func">OnSets</code> (<a href="../../doc/ref/chap41.html#X85AA04347CD117F9"><span class="RefLink">Reference: OnSets</span></a>) as third argument to a function like <code class="func">Stabilizer</code> (<a href="../../doc/ref/chap41.html#X797BD60E7ACEF1B1"><span class="RefLink">Reference: Stabilizers</span></a>), you have to make sure that the point (i.e. the second argument) is indeed a set. Otherwise you will get a puzzling error message or even wrong results! In the above example, the second argument <code class="code">blocks[1]</code> came from the function <code class="func">Blocks</code> (<a href="../../doc/ref/chap41.html#X84FE699F85371643"><span class="RefLink">Reference: Blocks</span></a>), which returns a list of sets, so everything was OK.</p>

<p>Actually there is a third block system of <code class="code">a8_56</code> that gives rise to a third subgroup.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">blocks := Blocks( a8_56, [1..56], [1,13] );;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">u28_56 := Stabilizer( a8_56, [1,13], OnSets );;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">u28 := PreImages( h56, u28_56 );;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Index( a8, u28 );</span>
28
</pre></div>

<p>We know that the subgroup <code class="code">u28</code> of index 28 is maximal, because we know that <code class="code">a8</code> has no subgroups of index 2, 4, or 7. However we can also quickly verify this by checking that <code class="code">a8_56</code> acts primitively on the 28 blocks.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">IsPrimitive( a8_56, blocks, OnSets );</span>
true
</pre></div>

<p><code class="func">Stabilizer</code> (<a href="../../doc/ref/chap41.html#X797BD60E7ACEF1B1"><span class="RefLink">Reference: Stabilizers</span></a>) is not only applicable to groups like <code class="code">a8</code> but also to their subgroups like <code class="code">u56</code>. So another method to find a new subgroup is to compute the stabilizer of another point in <code class="code">u56</code>. Note that <code class="code">u56</code> already leaves 1 and 2 fixed.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">u336 := Stabilizer( u56, 3 );;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Index( a8, u336 );</span>
336
</pre></div>

<p>Other functions are also applicable to subgroups. In the following we show that <code class="code">u336</code> acts regularly on the 60 triples of <code class="code">[ 4 .. 8 ]</code> which contain no element twice. We construct the list of these 60 triples with the function <code class="func">Orbit</code> (<a href="../../doc/ref/chap41.html#X80E0234E7BD79409"><span class="RefLink">Reference: Orbit</span></a>) (using <code class="func">OnTuples</code> (<a href="../../doc/ref/chap41.html#X832CC5F87EEA4A7E"><span class="RefLink">Reference: OnTuples</span></a>) as the natural generalization of <code class="func">OnPairs</code> (<a href="../../doc/ref/chap41.html#X80DAA1D2855B1456"><span class="RefLink">Reference: OnPairs</span></a>)) and then pass it as action domain to the function <code class="func">IsRegular</code> (<a href="../../doc/ref/chap41.html#X7CF02C4785F0EAB5"><span class="RefLink">Reference: IsRegular</span></a>). The positive result of the regularity test means that this action is equivalent to the actions of <code class="code">u336</code> on its 60 elements from the right.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">IsRegular( u336, Orbit( u336, [4,5,6], OnTuples ), OnTuples );</span>
true
</pre></div>

<p>Just as we did in the case of the action on the pairs above, we now construct a new permutation group that acts on <code class="code">[ 1 .. 336 ]</code> in the same way that <code class="code">a8</code> acts on the cosets of <code class="code">u336</code>. But this time we let <code class="code">a8</code> operate on a right transversal, just like <code class="code">norm</code> did in the natural homomorphism above.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">t := RightTransversal( a8, u336 );;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">a8_336 := Action( a8, t, OnRight );;</span>
</pre></div>

<p>To find subgroups above <code class="code">u336</code> we again look for nontrivial block systems.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">blocks := Blocks( a8_336, [1..336] );; blocks[1];</span>
[ 1, 43, 85 ]
</pre></div>

<p>We see that the union of <code class="code">u336</code> with its 43rd and its 85th coset is a subgroup in <code class="code">a8_336</code>, its index is 112. We can obtain it as the closure of <code class="code">u336</code> with a representative of the 43rd coset, which can be found as the 43rd element of the transversal <code class="code">t</code>. Note that in the representation <code class="code">a8_336</code> on 336 points, this subgroup corresponds to the stabilizer of the block <code class="code">[ 1, 43, 85 ]</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">u112 := ClosureGroup( u336, t[43] );;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Index( a8, u112 );</span>
112
</pre></div>

<p>Above this subgroup of index 112 lies a subgroup of index 56, which is not conjugate to <code class="code">u56</code>. In fact, unlike <code class="code">u56</code> it is maximal. We obtain this subgroup in the same way that we obtained <code class="code">u112</code>, this time forcing two points, namely 7 and 43 into the first block.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">blocks := Blocks( a8_336, [1..336], [1,7,43] );;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Length( blocks );</span>
56
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">u56b := ClosureGroup( u112, t[7] );; Index( a8, u56b );</span>
56
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">IsPrimitive( a8_336, blocks, OnSets );</span>
true
</pre></div>

<p>We already mentioned in Section <a href="chap5.html#X8493BB7D7ECB5AB2"><span class="RefLink">5.2</span></a> that there is another standard action of permutations, namely the conjugation. E.g., since no other action is specified in the following example, <code class="func">OrbitLength</code> (<a href="../../doc/ref/chap41.html#X799910CF832EDC45"><span class="RefLink">Reference: OrbitLength</span></a>) simply acts via <code class="func">OnPoints</code> (<a href="../../doc/ref/chap41.html#X7FE417DD837987B4"><span class="RefLink">Reference: OnPoints</span></a>), and because <var class="Arg">perm_1</var><code class="code"> ^ </code><var class="Arg">perm_2</var> is defined as the conjugation of <var class="Arg">perm_2</var> on <var class="Arg">perm_1</var>, in fact we compute the length of the conjugacy class of <code class="code">(1,2)(3,4)(5,6)(7,8)</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">OrbitLength( a8, (1,2)(3,4)(5,6)(7,8) );</span>
105
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">orb := Orbit( a8, (1,2)(3,4)(5,6)(7,8) );;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">u105 := Stabilizer( a8, (1,2)(3,4)(5,6)(7,8) );; Index( a8, u105 );</span>
105
</pre></div>

<p>Note that although the length of a conjugacy class of any element <span class="SimpleMath">g</span> in any finite group <span class="SimpleMath">G</span> can be computed as <code class="code">OrbitLength( </code><span class="SimpleMath">G</span><code class="code">, </code><span class="SimpleMath">g</span><code class="code"> )</code>, the command <code class="code">Size( ConjugacyClass( </code><span class="SimpleMath">G</span><code class="code">, </code><span class="SimpleMath">g</span><code class="code"> ) )</code> is probably more efficient.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Size( ConjugacyClass( a8, (1,2)(3,4)(5,6)(7,8) ) );</span>
105
</pre></div>

<p>Of course the stabilizer <code class="code">u105</code> is in fact the centralizer of the element <code class="code">(1,2)(3,4)(5,6)(7,8)</code>. <code class="func">Stabilizer</code> (<a href="../../doc/ref/chap41.html#X797BD60E7ACEF1B1"><span class="RefLink">Reference: Stabilizers</span></a>) notices that and computes the stabilizer using the centralizer algorithm for permutation groups. In the usual way we now look for the subgroups above <code class="code">u105</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">blocks := Blocks( a8, orb );; Length( blocks );</span>
15
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">blocks[1];</span>
[ (1,2)(3,4)(5,6)(7,8), (1,3)(2,4)(5,7)(6,8), (1,4)(2,3)(5,8)(6,7), 
  (1,5)(2,6)(3,7)(4,8), (1,6)(2,5)(3,8)(4,7), (1,7)(2,8)(3,5)(4,6), 
  (1,8)(2,7)(3,6)(4,5) ]
</pre></div>

<p>To find the subgroup of index 15 we again use closure. Now we must be a little bit careful to avoid confusion. <code class="code">u105</code> is the stabilizer of <code class="code">(1,2)(3,4)(5,6)(7,8)</code>. We know that there is a correspondence between the points of the orbit and the cosets of <code class="code">u105</code>. The point <code class="code">(1,2)(3,4)(5,6)(7,8)</code> corresponds to <code class="code">u105</code>. To get the subgroup above <code class="code">u105</code> that has index 15 in <code class="code">a8</code>, we must form the closure of <code class="code">u105</code> with an element of the coset that corresponds to any other point in the first block. If we choose the point <code class="code">(1,3)(2,4)(5,8)(6,7)</code>, we must use an element of <code class="code">a8</code> that maps <code class="code">(1,2)(3,4)(5,6)(7,8)</code> to <code class="code">(1,3)(2,4)(5,8)(6,7)</code>. The function <code class="func">RepresentativeAction</code> (<a href="../../doc/ref/chap41.html#X857DC7B085EB0539"><span class="RefLink">Reference: RepresentativeAction</span></a>) does what we need. It takes a group and two points and returns an element of the group that maps the first point to the second. In fact it also allows you to specify the action as an optional fourth argument as usual, but we do not need this here. If no such element exists in the group, i.e., if the two points do not lie in one orbit under the group, <code class="func">RepresentativeAction</code> (<a href="../../doc/ref/chap41.html#X857DC7B085EB0539"><span class="RefLink">Reference: RepresentativeAction</span></a>) returns <code class="keyw">fail</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">rep := RepresentativeAction( a8, (1,2)(3,4)(5,6)(7,8),</span>
<span class="GAPprompt">&gt;</span> <span class="GAPinput">                                       (1,3)(2,4)(5,8)(6,7) );</span>
(2,3)(6,8)
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">u15 := ClosureGroup( u105, rep );; Index( a8, u15 );</span>
15
</pre></div>

<p><code class="code">u15</code> is of course a maximal subgroup, because <code class="code">a8</code> has no subgroups of index 3 or 5. There is in fact another class of subgroups of index 15 above <code class="code">u105</code> that we get by adding <code class="code">(2,3)(6,7)</code> to <code class="code">u105</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">u15b := ClosureGroup( u105, (2,3)(6,7) );; Index( a8, u15b );</span>
15
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">RepresentativeAction( a8, u15, u15b );</span>
fail
</pre></div>

<p><code class="func">RepresentativeAction</code> (<a href="../../doc/ref/chap41.html#X857DC7B085EB0539"><span class="RefLink">Reference: RepresentativeAction</span></a>) tells us that there is no element <span class="SimpleMath">g</span> in <code class="code">a8</code> such that <code class="code">u15 ^ </code><span class="SimpleMath">g</span><code class="code"> = u15b</code>. Because <code class="code">^</code> also denotes the conjugation of subgroups this tells us that <code class="code">u15</code> and <code class="code">u15b</code> are not conjugate.</p>

<p><em>Summary.</em> In this section we have demonstrated some functions from the actions package. There is a whole class of functions that we did not mention, namely those that take a single element instead of a whole group as first argument, e.g., <code class="func">Cycle</code> (<a href="../../doc/ref/chap41.html#X80AF6E0683CA7F14"><span class="RefLink">Reference: Cycle</span></a>) and <code class="func">Permutation</code> (<a href="../../doc/ref/chap41.html#X7807A33381DCAB26"><span class="RefLink">Reference: Permutation</span></a>). These are fully described in Chapter <a href="../../doc/ref/chap41.html#X87115591851FB7F4"><span class="RefLink">Reference: Group Actions</span></a>.</p>

<p><a id="X8131EE9182385680" name="X8131EE9182385680"></a></p>

<h4>5.4 <span class="Heading">Group Homomorphisms by Images</span></h4>

<p>We have already seen examples of group homomorphisms in the last sections, namely natural homomorphisms and action homomorphisms. In this section we will show how to construct a group homomorphism <span class="SimpleMath">G → H</span> by specifying a generating set for <span class="SimpleMath">G</span> and the images of these generators in <span class="SimpleMath">H</span>. We use the function <code class="code">GroupHomomorphismByImages( <var class="Arg">G</var>, <var class="Arg">H</var>, <var class="Arg">gens</var>, <var class="Arg">imgs</var> )</code> where <var class="Arg">gens</var> is a generating set for <var class="Arg">G</var> and <var class="Arg">imgs</var> is a list whose <span class="SimpleMath">i</span>th entry is the image of <span class="SimpleMath"><var class="Arg">gens</var>[i]</span> under the homomorphism.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">s4 := Group((1,2,3,4),(1,2));; s3 := Group((1,2,3),(1,2));;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">hom := GroupHomomorphismByImages( s4, s3,</span>
<span class="GAPprompt">&gt;</span> <span class="GAPinput">          GeneratorsOfGroup(s4), [(1,2),(2,3)] );</span>
[ (1,2,3,4), (1,2) ] -&gt; [ (1,2), (2,3) ]
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Kernel( hom );</span>
Group([ (1,4)(2,3), (1,3)(2,4) ])
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Image( hom, (1,2,3) );</span>
(1,2,3)
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Image( hom, DerivedSubgroup(s4) );</span>
Group([ (1,3,2), (1,3,2) ])
</pre></div>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">PreImage( hom, (1,2,3) );</span>
Error, &lt;map&gt; must be an inj. and surj. mapping called from
&lt;function&gt;( &lt;arguments&gt; ) called from read-eval-loop
Entering break read-eval-print loop ...
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue
<span class="GAPbrkprompt">brk&gt;</span> <span class="GAPinput">quit;</span>
</pre></div>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">PreImagesRepresentative( hom, (1,2,3) );</span>
(1,4,2)
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">PreImage( hom, TrivialSubgroup(s3) );  # the kernel</span>
Group([ (1,4)(2,3), (1,3)(2,4) ])
</pre></div>

<p>This homomorphism from <span class="SimpleMath">S_4</span> onto <span class="SimpleMath">S_3</span> is well known from elementary group theory. Images of elements and subgroups under <code class="code">hom</code> can be calculated with the function <code class="func">Image</code> (<a href="../../doc/ref/chap32.html#X87F4D35A826599C6"><span class="RefLink">Reference: Image</span></a>). But since the mapping <code class="code">hom</code> is not bijective, we cannot use the function <code class="func">PreImage</code> (<a href="../../doc/ref/chap32.html#X836FAEAC78B55BF4"><span class="RefLink">Reference: PreImage</span></a>) for preimages of elements (they can have several preimages). Instead, we have to use <code class="func">PreImagesRepresentative</code> (<a href="../../doc/ref/chap32.html#X7AE24A1586B7DE79"><span class="RefLink">Reference: PreImagesRepresentative</span></a>), which returns one preimage if at least one exists (and would return <code class="keyw">fail</code> if none exists, which cannot occur for our surjective <code class="code">hom</code>). On the other hand, we can use <code class="func">PreImage</code> (<a href="../../doc/ref/chap32.html#X836FAEAC78B55BF4"><span class="RefLink">Reference: PreImage</span></a>) for the preimage of a set (which always exists, even if it is empty).</p>

<p>Suppose we mistype the input when trying to construct a homomorphism as below.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">GroupHomomorphismByImages( s4, s3,</span>
<span class="GAPprompt">&gt;</span> <span class="GAPinput">       GeneratorsOfGroup(s4), [(1,2,3),(2,3)] );</span>
fail
</pre></div>

<p>There is no such homomorphism, hence <code class="keyw">fail</code> is returned. But note that because of this, <code class="func">GroupHomomorphismByImages</code> (<a href="../../doc/ref/chap40.html#X7F348F497C813BE0"><span class="RefLink">Reference: GroupHomomorphismByImages</span></a>) must do some checks, and this was also done for the mapping <code class="code">hom</code> above. One can avoid these checks if one is sure that the desired homomorphism really exists. For that, the function <code class="func">GroupHomomorphismByImagesNC</code> (<a href="../../doc/ref/chap40.html#X7AB15AF5830F2A6B"><span class="RefLink">Reference: GroupHomomorphismByImagesNC</span></a>) can be used; the <code class="code">NC</code> stands for "no check".</p>

<p>But note that horrible things can happen if <code class="func">GroupHomomorphismByImagesNC</code> (<a href="../../doc/ref/chap40.html#X7AB15AF5830F2A6B"><span class="RefLink">Reference: GroupHomomorphismByImagesNC</span></a>) is used when the input does not describe a homomorphism.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">hom2 := GroupHomomorphismByImagesNC( s4, s3,</span>
<span class="GAPprompt">&gt;</span> <span class="GAPinput">           GeneratorsOfGroup(s4), [(1,2,3),(2,3)] );</span>
[ (1,2,3,4), (1,2) ] -&gt; [ (1,2,3), (2,3) ]
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">Size( Kernel(hom2) );</span>
24
</pre></div>

<p>In other words, <strong class="pkg">GAP</strong> claims that the kernel is the full <code class="code">s4</code>, yet <code class="code">hom2</code> obviously has some non-trivial images! Clearly there is no such thing as a homomorphism which maps an element of order 4 (namely, (1,2,3,4)) to an element of order 3 (namely, (1,2,3)). <em>But if you use the command <code class="func">GroupHomomorphismByImagesNC</code> (<a href="../../doc/ref/chap40.html#X7AB15AF5830F2A6B"><span class="RefLink">Reference: GroupHomomorphismByImagesNC</span></a>), <strong class="pkg">GAP</strong> trusts you.</em></p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">IsGroupHomomorphism( hom2 );</span>
true
</pre></div>

<p>And then it produces serious nonsense if the thing is not a homomorphism, as seen above!</p>

<p>Besides the safe command <code class="func">GroupHomomorphismByImages</code> (<a href="../../doc/ref/chap40.html#X7F348F497C813BE0"><span class="RefLink">Reference: GroupHomomorphismByImages</span></a>), which returns <code class="keyw">fail</code> if the requested homomorphism does not exist, there is the function <code class="func">GroupGeneralMappingByImages</code> (<a href="../../doc/ref/chap40.html#X7A59F2C47BD41DC8"><span class="RefLink">Reference: GroupGeneralMappingByImages</span></a>), which returns a general mapping (that is, a possibly multi-valued mapping) that can be tested with <code class="func">IsGroupHomomorphism</code> (<a href="../../doc/ref/chap32.html#X819DD174829BF3AE"><span class="RefLink">Reference: IsGroupHomomorphism</span></a>).</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">hom2 := GroupGeneralMappingByImages( s4, s3,</span>
<span class="GAPprompt">&gt;</span> <span class="GAPinput">           GeneratorsOfGroup(s4), [(1,2,3),(2,3)] );;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">IsGroupHomomorphism( hom2 );</span>
false
</pre></div>

<p>But the possibility of testing for being a homomorphism is not the only reason why <strong class="pkg">GAP</strong> offers <em>group general mappings</em>. Another (more important?) reason is that their existence allows "reversal of arrows" in a homomorphism such as our original <code class="code">hom</code>. By this we mean the <code class="func">GroupHomomorphismByImages</code> (<a href="../../doc/ref/chap40.html#X7F348F497C813BE0"><span class="RefLink">Reference: GroupHomomorphismByImages</span></a>) with left and right sides exchanged, in which case it is of course merely a <code class="func">GroupGeneralMappingByImages</code> (<a href="../../doc/ref/chap40.html#X7A59F2C47BD41DC8"><span class="RefLink">Reference: GroupGeneralMappingByImages</span></a>).</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">rev := GroupGeneralMappingByImages( s3, s4,</span>
<span class="GAPprompt">&gt;</span> <span class="GAPinput">          [(1,2),(2,3)], GeneratorsOfGroup(s4) );;</span>
</pre></div>

<p>Now <span class="SimpleMath">hom</span> maps <span class="SimpleMath">a</span> to <span class="SimpleMath">b</span> if and only if <span class="SimpleMath">rev</span> maps <span class="SimpleMath">b</span> to <span class="SimpleMath">a</span>, for <span class="SimpleMath">a ∈</span> <code class="code">s4</code> and <span class="SimpleMath">b ∈</span> <code class="code">s3</code>. Since every such <span class="SimpleMath">b</span> has four preimages under <code class="code">hom</code>, it now has four images under <code class="code">rev</code>. Just as the four preimages form a coset of the kernel <span class="SimpleMath">V_4 ≤</span><code class="code">s4</code> of <code class="code">hom</code>, they also form a coset of the <em>cokernel</em> <span class="SimpleMath">V_4 ≤</span><code class="code">s4</code> of <code class="code">rev</code>. The cokernel itself is the set of all images of <code class="code">One( s3 )</code>. (It is a normal subgroup in the group of all images under <code class="code">rev</code>.) The operation <code class="func">One</code> (<a href="../../doc/ref/chap31.html#X8046262384895B2A"><span class="RefLink">Reference: One</span></a>) returns the identity element of a group. And this is why <strong class="pkg">GAP</strong> wants to perform such a reversal of arrows: it calculates the kernel of a homomorphism like <code class="code">hom</code> as the cokernel of the reversed group general mapping (here <code class="code">rev</code>).</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">CoKernel( rev );</span>
Group([ (1,4)(2,3), (1,3)(2,4) ])
</pre></div>

<p>The reason why <code class="code">rev</code> is not a homomorphism is that it is not single-valued (because <code class="code">hom</code> was not injective). But there is another critical condition: If we reverse the arrows of a non-surjective homomorphism, we obtain a group general mapping which is not defined everywhere, i.e., which is not total (although it will be single-valued if the original homomorphism is injective). <strong class="pkg">GAP</strong> requires that a group homomorphism be both single-valued and total, so you will get <code class="keyw">fail</code> if you say <code class="code">GroupHomomorphismByImages( <var class="Arg">G</var>, <var class="Arg">H</var>, <var class="Arg">gens</var>, <var class="Arg">imgs</var> )</code> where <var class="Arg">gens</var> does not generate <var class="Arg">G</var> (even if this would give a decent homomorphism on the subgroup generated by <var class="Arg">gens</var>). For a full description, see Chapter <a href="../../doc/ref/chap40.html#X83702FC27B3C3098"><span class="RefLink">Reference: Group Homomorphisms</span></a>.</p>

<p>The last example of this section shows that the notion of kernel and cokernel naturally extends even to the case where neither <code class="code">hom2</code> nor its inverse general mapping (with arrows reversed) is a homomorphism.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">CoKernel( hom2 );  Kernel( hom2 );</span>
Group([ (2,3), (1,3) ])
Group([ (3,4), (2,3,4), (1,2,4) ])
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">IsGroupHomomorphism( InverseGeneralMapping( hom2 ) );</span>
false
</pre></div>

<p><em>Summary.</em> In this section we have constructed homomorphisms by specifying images for a set of generators. We have seen that by reversing the direction of the mapping, we get group general mappings, which need not be single-valued (unless the mapping was injective) nor total (unless the mapping was surjective).</p>

<p><a id="X7FFD731684606BC6" name="X7FFD731684606BC6"></a></p>

<h4>5.5 <span class="Heading">Nice Monomorphisms</span></h4>

<p>For some types of groups, the best method to calculate in an isomorphic group in a "better" representation (say, a permutation group). We call an injective homomorphism, that will give such an isomorphic image a "nice monomorphism".</p>

<p>For example in the case of a matrix group we can take the action on the underlying vector space (or a suitable subset) to obtain such a monomorphism:</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">grp:=GL(2,3);;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">dom:=GF(3)^2;;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">hom := ActionHomomorphism( grp, dom );; IsInjective( hom );</span>
true
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">p := Image( hom,grp );</span>
Group([ (4,7)(5,8)(6,9), (2,7,6)(3,4,8) ])
</pre></div>

<p>To demonstrate the technique of nice monomorphisms, we compute the conjugacy classes of the permutation group and lift them back into the matrix group with the monomorphism <code class="code">hom</code>. Lifting back a conjugacy class means finding the preimage of the representative and of the centralizer; the latter is called <code class="func">StabilizerOfExternalSet</code> (<a href="../../doc/ref/chap41.html#X7BAFF02B7D6DF9F2"><span class="RefLink">Reference: StabilizerOfExternalSet</span></a>) in <strong class="pkg">GAP</strong> (because conjugacy classes are represented as external sets, see Section <a href="../../doc/ref/chap39.html#X7D474F8F87E4E5D9"><span class="RefLink">Reference: Conjugacy Classes</span></a>).</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">pcls := ConjugacyClasses( p );; gcls := [  ];;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">for pc  in pcls  do</span>
<span class="GAPprompt">&gt;</span> <span class="GAPinput">     gc:=ConjugacyClass(grp,</span>
<span class="GAPprompt">&gt;</span> <span class="GAPinput">                  PreImagesRepresentative(hom,Representative(pc)));</span>
<span class="GAPprompt">&gt;</span> <span class="GAPinput">     SetStabilizerOfExternalSet(gc,PreImage(hom,</span>
<span class="GAPprompt">&gt;</span> <span class="GAPinput">                                     StabilizerOfExternalSet(pc)));</span>
<span class="GAPprompt">&gt;</span> <span class="GAPinput">     Add( gcls, gc );</span>
<span class="GAPprompt">&gt;</span> <span class="GAPinput">   od;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">List( gcls, Size );</span>
[ 1, 8, 12, 1, 8, 6, 6, 6 ]
</pre></div>

<p>All the steps we have made above are automatically performed by <strong class="pkg">GAP</strong> if you simply ask for <code class="code">ConjugacyClasses( grp )</code>, provided that <strong class="pkg">GAP</strong> already knows that <code class="code">grp</code> is finite (e.g., because you asked <code class="code">IsFinite( grp )</code> before). The reason for this is that a finite matrix group like <code class="code">grp</code> is "handled by a nice monomorphism". For such groups, <strong class="pkg">GAP</strong> uses the command <code class="func">NiceMonomorphism</code> (<a href="../../doc/ref/chap40.html#X7965086E82ABCF41"><span class="RefLink">Reference: NiceMonomorphism</span></a>) to construct a monomorphism (such as the <code class="code">hom</code> in the previous example) and then proceeds as we have done above.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">grp:=GL(2,3);;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">IsHandledByNiceMonomorphism( grp );</span>
true
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">hom := NiceMonomorphism( grp );</span>
&lt;action isomorphism&gt;
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">p :=Image(hom,grp);</span>
Group([ (4,7)(5,8)(6,9), (2,7,6)(3,4,8) ])
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">cc := ConjugacyClasses( grp );; ForAll(cc, x-&gt; x in gcls); </span>
true
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">ForAll(gcls, x-&gt;x in cc); # cc and gcls might be ordered differently</span>
true
</pre></div>

<p>Note that a nice monomorphism might be defined on a larger group than <code class="code">grp</code> –so we have to use <code class="code">Image( hom, grp )</code> and not only <code class="code">Image( hom )</code>.</p>

<p>Nice monomorphisms are not only used for matrix groups, but also for other kinds of groups in which one cannot calculate easily enough. As another example, let us show that the automorphism group of the quaternion group of order 8 is isomorphic to the symmetric group of degree 4 by examining the "nice object" associated with that automorphism group.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">p:=Group((1,7,6,8)(2,5,3,4), (1,2,6,3)(4,8,5,7));;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">aut := AutomorphismGroup( p );; NiceMonomorphism(aut);;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">niceaut := NiceObject( aut );</span>
Group([ (1,4,2,3), (1,5,4)(2,6,3), (1,2)(3,4), (3,4)(5,6) ])
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">IsomorphismGroups( niceaut, SymmetricGroup( 4 ) );</span>
[ (1,4,2,3), (1,5,4)(2,6,3), (1,2)(3,4), (3,4)(5,6) ] -&gt; 
[ (1,2,4,3), (1,4,3), (1,4)(2,3), (1,3)(2,4) ]
</pre></div>

<p>The range of a nice monomorphism is in most cases a permutation group, because nice monomorphisms are mostly action homomorphisms. In some cases, like in our last example, the group is solvable and you might prefer a pc group as nice object. You cannot change the nice monomorphism of the automorphism group (because it is the value of the attribute <code class="func">NiceMonomorphism</code> (<a href="../../doc/ref/chap40.html#X7965086E82ABCF41"><span class="RefLink">Reference: NiceMonomorphism</span></a>)), but you can compose it with an isomorphism from the permutation group to a pc group to obtain your personal nicer monomorphism. If you reconstruct the automorphism group, you can even prescribe it this nicer monomorphism as its <code class="func">NiceMonomorphism</code> (<a href="../../doc/ref/chap40.html#X7965086E82ABCF41"><span class="RefLink">Reference: NiceMonomorphism</span></a>), because a newly-constructed group will not yet have a <code class="func">NiceMonomorphism</code> (<a href="../../doc/ref/chap40.html#X7965086E82ABCF41"><span class="RefLink">Reference: NiceMonomorphism</span></a>) set.</p>


<div class="example"><pre>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">nicer := NiceMonomorphism(aut) * IsomorphismPcGroup(niceaut);;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">aut2 := GroupByGenerators( GeneratorsOfGroup( aut ) );;</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">SetIsHandledByNiceMonomorphism( aut2, true );</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">SetNiceMonomorphism( aut2, nicer );</span>
<span class="GAPprompt">gap&gt;</span> <span class="GAPinput">NiceObject( aut2 );  # a pc group</span>
Group([ f1*f2, f2^2*f3, f4, f3 ])
</pre></div>

<p>The star <code class="code">*</code> denotes composition of mappings from the left to the right, as we have seen in Section <a href="chap5.html#X8493BB7D7ECB5AB2"><span class="RefLink">5.2</span></a> above. Reconstructing the automorphism group may of course result in the loss of other information <strong class="pkg">GAP</strong> had already gathered, besides the (not-so-)nice monomorphism.</p>

<p><em>Summary.</em> In this section we have seen how calculations in groups can be carried out in isomorphic images in nicer groups. We have seen that <strong class="pkg">GAP</strong> pursues this technique automatically for certain classes of groups, e.g., for matrix groups that are known to be finite.</p>

<p><a id="X84579FB48474079C" name="X84579FB48474079C"></a></p>

<h4>5.6 <span class="Heading">Further Information about Groups and Homomorphisms</span></h4>

<p>Groups and the functions for groups are treated in Chapter <a href="../../doc/ref/chap39.html#X8716635F7951801B"><span class="RefLink">Reference: Groups</span></a>. There are several chapters dealing with groups in specific representations, for example Chapter <a href="../../doc/ref/chap43.html#X85ED46007CED6191"><span class="RefLink">Reference: Permutation Groups</span></a> on permutation groups, <a href="../../doc/ref/chap45.html#X86007B0083F60470"><span class="RefLink">Reference: Polycyclic Groups</span></a> on polycyclic (including finite solvable) groups, <a href="../../doc/ref/chap44.html#X7CF51CB48610A07D"><span class="RefLink">Reference: Matrix Groups</span></a> on matrix groups and <a href="../../doc/ref/chap47.html#X7AA982637E90B35A"><span class="RefLink">Reference: Finitely Presented Groups</span></a> on finitely presented groups. Chapter <a href="../../doc/ref/chap41.html#X87115591851FB7F4"><span class="RefLink">Reference: Group Actions</span></a> deals with group actions. Group homomorphisms are the subject of Chapter <a href="../../doc/ref/chap40.html#X83702FC27B3C3098"><span class="RefLink">Reference: Group Homomorphisms</span></a>.</p>


<div class="chlinkprevnextbot">&nbsp;<a href="chap0.html">[Top of Book]</a>&nbsp;  <a href="chap0.html#contents">[Contents]</a>&nbsp;  &nbsp;<a href="chap4.html">[Previous Chapter]</a>&nbsp;  &nbsp;<a href="chap6.html">[Next Chapter]</a>&nbsp;  </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="chap8.html">8</a>  <a href="chapBib.html">Bib</a>  <a href="chapInd.html">Ind</a>  </div>

<hr />
<p class="foot">generated by <a href="http://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>