chap5.txt

  
  5 Groups and Homomorphisms
  
  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  Group  (Reference:  Groups),  Size
  (Reference:  Size) or SylowSubgroup (Reference: SylowSubgroup), however, are
  the  same for all kinds of groups, although the algorithms which compute the
  information of course will be different in most cases.
  
  
  5.1 Permutation groups
  
  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:
  
    Example  
    gap> s8 := Group( (1,2), (1,2,3,4,5,6,7,8) );
    Group([ (1,2), (1,2,3,4,5,6,7,8) ])
  
  
  We   formed   the   group   generated   by   the   permutations   (1,2)  and
  (1,2,3,4,5,6,7,8),  which  is  well  known  to be the symmetric group S_8 on
  eight  points,  and  assigned  it to the identifier s8. Now S_8 contains the
  alternating  group  on  eight points which can be described in several ways,
  e.g.,  as  the  group  of  all  even  permutations  in s8, or as its derived
  subgroup.  Once  we ask GAP to verify that the group is an alternating group
  acting  in  its  natural permutation representation, the system will display
  the group accordingly.
  
    Example  
    gap> a8 := DerivedSubgroup( s8 );
    Group([ (1,2,3), (2,3,4), (2,4)(3,5), (2,6,4), (2,4)(5,7), 
      (2,8,6,4)(3,5) ])
    gap> Size( a8 ); IsAbelian( a8 ); IsPerfect( a8 );
    20160
    false
    true
    gap> IsNaturalAlternatingGroup(a8);
    true
    gap> a8;
    Alt( [ 1 .. 8 ] )
  
  
  Once information about a group like s8 or a8 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, a8
  stores  its  order  and that it is nonabelian and perfect, and s8 stores its
  derived  subgroup  a8.  Had  we computed a8 as CommutatorSubgroup( s8, s8 ),
  however,  it  would  not  have  been stored, because it would then have been
  computed  as  a function of two arguments, and hence one could not attribute
  it  to  just  one  of  them.  (Of  course  the  function  CommutatorSubgroup
  (Reference:  CommutatorSubgroup)  can compute the commutator subgroup of two
  arbitrary   subgroups.)   The   situation  is  a  bit  different  for  Sylow
  p-subgroups:  The  function  SylowSubgroup  (Reference:  SylowSubgroup) also
  requires  two  arguments,  namely  a  group and a prime p, but the result is
  stored  in the group –namely together with the prime p in a list that can be
  accessed  with  ComputedSylowSubgroups,  but  we  won't dwell on the details
  here.
  
    Example  
    gap> syl2 := SylowSubgroup( a8, 2 );; Size( syl2 );
    64
    gap> Normalizer( a8, syl2 ) = syl2;
    true
    gap> cent := Centralizer( a8, Centre( syl2 ) );; Size( cent );
    192
    gap> DerivedSeries( cent );; List( last, Size );
    [ 192, 96, 32, 2, 1 ]
  
  
  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.
  
  With  the  next  examples,  we  want to calculate a subgroup of a8, 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 2^3.
  
    Example  
    gap> elab := Group( (1,2)(3,4)(5,6)(7,8), (1,3)(2,4)(5,7)(6,8),
    >                   (1,5)(2,6)(3,7)(4,8) );;
    gap> Size( elab );
    8
    gap> IsElementaryAbelian( elab );
    true
  
  
  As  usual,  GAP  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 us
  to  specify a particular group to GAP, by using well-chosen identifiers such
  as  a8  and  elab,  it  is  impossible for GAP 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
  SetName  (Reference:  SetName).  We  do  this  with  the name 2^3 here which
  reflects the mathematical properties of the group. From now on, GAP will use
  this  name when printing the group for us, but we still cannot use this name
  to  specify  the group to GAP, 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.
  
    Example  
    gap> SetName( elab, "<group of type 2^3>" ); elab;
    <group of type 2^3>
    gap> norm := Normalizer( a8, elab );; Size( norm );
    1344
  
  
  Now  that  we have the subgroup norm of order 1344 and its subgroup elab, we
  want  to  look at its factor group. But since we also want to find preimages
  of  factor  group  elements  in  norm, we really want to look at the natural
  homomorphism  defined on norm with kernel elab and whose image is the factor
  group.
  
    Example  
    gap> hom := NaturalHomomorphismByNormalSubgroup( norm, elab );
    <action epimorphism>
    gap> f := Image( hom );
    Group([ (), (), (), (4,5)(6,7), (4,6)(5,7), (2,3)(6,7), (2,4)(3,5), 
     (1,2)(5,6) ])
    gap> Size( f );
    168
  
  
  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  hom). However, the action domain of this
  factor  group  has  nothing  to  do with the action domain of norm. (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 hom is a coset modulo elab. We use the function PreImages
  (Reference: PreImages) here because hom is not a bijection, so an element of
  the range can have several preimages or none at all.
  
    Example  
    gap> ker:= Kernel( hom );
    <group of type 2^3>
    gap> x := (1,8,3,5,7,6,2);; Image( hom, x );
    (1,7,5,6,2,3,4)
    gap> coset := PreImages( hom, last );
    RightCoset(<group of type 2^3>,(2,8,6,7,3,4,5))
  
  
  Note  that  GAP  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.
  
    Example  
    gap> rep:= Representative( coset );
    (2,8,6,7,3,4,5)
    gap> x * rep^-1 in ker;
    true
  
  
  The  factor  group  f  is a simple group, i.e., it has no non-trivial normal
  subgroups.  GAP  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.)
  
    Example  
    gap> IsSimple( f ); IsomorphismTypeInfoFiniteSimpleGroup( f );
    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" )
    gap> SetName( f, "L_3(2)" );
  
  
  We  give  f the name L_3(2) because the last part of the name string reveals
  that  it  is  isomorphic  to  the  simple  linear  group L_3(2). This group,
  however,  also  has  a lot of other names. Names that are connected with a =
  sign  are different names for the same matrix group, e.g., A(2,2) is the Lie
  type  notation  for  the classical notation L(3,2). Other pairs of names are
  connected  via  ~,  these  then  specify  other  classical  groups  that are
  isomorphic  to  that  linear group (e.g., the symplectic group S(2,7), whose
  Lie type notation would be C(1,7)).
  
  The  group  norm  acts  on the eight elements of its normal subgroup elab by
  conjugation,  yielding  a  representation  of  L_3(2) in s8 which leaves one
  point  fixed  (namely  point 1).  The  image  of  this representation can be
  computed  with  the function Action (Reference: Action homomorphisms); it is
  even contained in the group norm and we can show that norm is indeed a split
  extension of the elementary abelian group 2^3 with this image of L_3(2).
  
    Example  
    gap> op := Action( norm, elab );
    Group([ (), (), (), (5,6)(7,8), (5,7)(6,8), (3,4)(7,8), (3,5)(4,6), 
      (2,3)(6,7) ])
    gap> IsSubgroup( a8, op ); IsSubgroup( norm, op );
    true
    true
    gap> IsTrivial( Intersection( elab, op ) );
    true
    gap> SetName( norm, "2^3:L_3(2)" );
  
  
  By  the  way,  you  should  not  try  the operator < instead of the function
  IsSubgroup (Reference: IsSubgroup). Something like
  
    Example  
    gap> elab < a8;
    false
  
  
  will  not cause an error, but the result does not signify anything about the
  inclusion  of  one group in another; < tests which of the two groups is less
  in some total order. On the other hand, the equality operator = in fact does
  test the equality of its arguments.
  
  Summary.  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 GAP uses
  these names when printing the groups.
  
  
  5.2 Actions of Groups
  
  In  order  to  get another representation of a8, we consider another action,
  namely that on the elements of a certain conjugacy class by conjugation.
  
  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.
  
    Example  
    gap> ccl := ConjugacyClasses( a8 );; Length( ccl );
    14
    gap> List( ccl, c -> Order( Representative( c ) ) );
    [ 1, 2, 2, 3, 6, 3, 4, 4, 5, 15, 15, 6, 7, 7 ]
    gap> List( ccl, Size );
    [ 1, 210, 105, 112, 1680, 1120, 2520, 1260, 1344, 1344, 1344, 3360, 
      2880, 2880 ]
  
  
  Note  the  difference  between  Order  (Reference:  Order)  (which means the
  element  order),  Size  (Reference:  Size)  (which  means  the  size  of the
  conjugacy class) and Length (Reference: Length) (which means the length of a
  list). We choose to let a8 operate on the class of length 112.
  
    Example  
    gap> class := First( ccl, c -> Size(c) = 112 );;
    gap> op := Action( a8, AsList( class ),OnPoints );;
  
  
  We use AsList (Reference: AsList) here to convert the conjugacy class into a
  list  of  its elements whereas we wrote Action( norm, elab ) directly in the
  previous  section.  The reason is that the elementary abelian group elab can
  be  quickly  enumerated  by  GAP whereas the standard enumeration method for
  conjugacy  classes is slower than just explicit calculation of the elements.
  However,  GAP  is reluctant to construct explicit element lists, because for
  really large groups this direct method is infeasible.
  
  Note  also  the  function  First  (Reference: First), used to find the first
  element in a list which passes some test.
  
  In  this example, we have specified the action function OnPoints (Reference:
  OnPoints)  in  this  example,  which is defined as OnPoints( d, g ) = d ^ g.
  This caret operator denotes conjugation in a group if both arguments d and g
  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   OnRight   (Reference:   OnRight),   which   means   right
  multiplication,  defined as d * g. (Group actions in GAP are always from the
  right.)
  
  We now have a permutation representation op 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 Blocks
  (Reference: Blocks).
  
    Example  
    gap> IsPrimitive( op, [ 1 .. 112 ] );
    false
    gap> blocks := Blocks( op, [ 1 .. 112 ] );;
  
  
  Note that we must specify the domain of the action. You might think that the
  functions   IsPrimitive  (Reference:  IsPrimitive)  and  Blocks  (Reference:
  Blocks) could use [ 1 .. 112 ] as default domain if no domain was given. But
  this  is not so easy, for example would the default domain of Group( (2,3,4)
  )  be  [  1  ..  4 ] or [ 2 .. 4 ]? To avoid confusion, all action functions
  require  that  you  specify the domain of action. If we had specified [ 1 ..
  113  ]  in  the primitivity test above, point 113 would have been a fixpoint
  (and the action would not even have been transitive).
  
  Now  blocks  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 op act on these
  blocks setwise.
  
    Example  
    gap> Length( blocks[1] );  Length( blocks );
    2
    56
    gap> op2 := Action( op, blocks, OnSets );;
    gap> IsPrimitive( op2, [ 1 .. 56 ] );
    true
  
  
  Note  that  we give a third argument (the action function OnSets (Reference:
  OnSets)) to indicate that the action is not the default action on points but
  an  action  on  sets of elements given as sorted lists. (Section 'Reference:
  Basic Actions' lists all actions that are pre-defined by GAP.)
  
  The  action  of op 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 *
  operator, reading left-to-right.
  
    Example  
    gap> ophom := ActionHomomorphism( a8, op );;
    gap> ophom2 := ActionHomomorphism( op, op2 );;
    gap> composition := ophom * ophom2;;
    gap> stab := Stabilizer( op2, 2 );;
    gap> preim := PreImages( composition, stab );
    Group([ (1,4,2), (3,6,7), (3,8,5,7,6), (1,4)(7,8) ])
  
  
  Alternatively,  it  is  possible  to create action homomorphisms immediately
  (without  creating  the action first) by giving the same set of arguments to
  ActionHomomorphism (Reference: ActionHomomorphism).
  
    Example  
    gap> nophom := ActionHomomorphism( a8, AsList(class) );
    <action homomorphism>
    gap> IsSurjective(nophom);
    false
    gap> Image(nophom,(1,2,3));
    (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)
  
  
  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  Image  of the action, but into the full symmetric group, i.e. it is not
  automatically  surjective. Surjectivity can be enforced by giving the string
  "surjective" as an extra last argument. The Image of the action homomorphism
  of course is the same group in either case.
  
    Example  
    gap> Size(Range(nophom));
    1974506857221074023536820372759924883412778680349753377966562950949028\
    5896977181144089422435502777936659795733823785363827233491968638562181\
    1850780464277094400000000000000000000000000
    gap> Size(Range(ophom));
    20160
    gap> nophom := ActionHomomorphism( a8, AsList(class),"surjective" );
    <action epimorphism>
    gap> Size(Range(nophom));
    20160
  
  
  Continuing  the example, the normalizer of an element in the conjugacy class
  class  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 a8 is
  found      by      the     function     RepresentativeAction     (Reference:
  RepresentativeAction).
  
    Example  
    gap> sgp := Normalizer( a8, Subgroup(a8,[Representative(class)]) );;
    gap> Size( sgp );
    360
    gap> RepresentativeAction( a8, sgp, preim );
    (2,4,3)
  
  
  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.
  
    Example  
    gap> cosets:=RightCosets(a8,norm);;
    gap> op:=Action(a8,cosets,OnRight);
    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) ])
    gap> NrMovedPoints(op);
    15
  
  
  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,
  GAP  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 enumerator. The easiest example of this concept is the Enumerator
  (Reference:  Enumerator)  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:
  
    Example  
    gap> enum:=Enumerator(SymmetricGroup(20));
    <enumerator of perm group>
    gap> Length(enum);
    2432902008176640000
    gap> enum[123456789012345];
    (1,4,15,3,14,11,8,17,6,18,5,7,20,13,10,9,2,12)
    gap> Position(enum,(1,2,3,4,5,6,7,8,9,10));
    71948729603
  
  
  For  the  action  on  cosets  the object of interest is the RightTransversal
  (Reference:  RightTransversal)  of  a subgroup. Again, it does not write out
  actual elements and thus can be created even for subgroups of large index.
  
    Example  
    gap> t:=RightTransversal(a8,norm);
    RightTransversal(Alt( [ 1 .. 8 ] ),2^3:L_3(2))
    gap> t[7];
    (4,6,5)
    gap> Position(t,(4,6,7,8,5));
    8
    gap> Position(t,(1,2,3));
    fail
  
  
  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  PositionCanonical  (Reference: PositionCanonical) instead of
  Position  (Reference:  Position).  In  general,  for elements contained in a
  list,  PositionCanonical  (Reference: PositionCanonical) returns the same as
  Position.  If  the  element  is  not  contained in the list (and for special
  lists,  such  as  transversals),  PositionCanonical returns the list element
  representing the same objects, e.g. the transversal element representing the
  same coset.
  
    Example  
    gap> PositionCanonical(t,(1,2,3));
    2
    gap> t[2];
    (6,7,8)
    gap> t[2]/(1,2,3);
    (1,3,2)(6,7,8)
    gap> last in norm;
    true
  
  
  Thus,  acting on a RightTransversal with the OnRight 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.
  
    Example  
    gap> Action(a8,RightTransversal(a8,norm),OnRight);
    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) ])
  
  
  Summary.  In  this  section  we  have  learned how groups can operate on GAP
  objects such as integers and group elements. We have used ActionHomomorphism
  (Reference:    ActionHomomorphism),   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.
  
  
  5.3 Subgroups as Stabilizers
  
  Action  functions  can  also  be used without constructing external sets. We
  will try to find several subgroups in a8 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.
  
    Example  
    gap> u8 := Stabilizer( a8, 1 );
    Group([ (2,3,4,5,6,7,8), (2,4,5,6,7,8,3) ])
    gap> Index( a8, u8 );
    8
    gap> Orbit( a8, 1 ); Length( last );
    [ 1, 3, 2, 4, 5, 6, 7, 8 ]
    8
  
  
  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 Tuples (Reference:
  Tuples) we first generate a list of all pairs.
  
    Example  
    gap> pairs := Tuples( [1..8], 2 );;
  
  
  Now  we  would like to have a8 operate on this domain. But we cannot use the
  default  action  OnPoints (Reference: OnPoints) because powering a list by a
  permutation  via  the  caret  operator ^ 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 GAP
  functionality  for  group  actions, not to a GAP package). In our example we
  can  do  this  by simply passing OnPairs (Reference: OnPairs) as an optional
  last  argument.  All  functions  from  the  actions  package  accept such an
  optional  argument  that  describes  the action. One example is IsTransitive
  (Reference: IsTransitive).
  
    Example  
    gap> IsTransitive( a8, pairs, OnPairs );
    false
  
  
  The  action is of course not transitive, since the pairs [ 1, 1 ] and [ 1, 2
  ]  cannot lie in the same orbit. So we want to find out what the orbits are.
  The  function Orbits (Reference: Orbits) does that for us. It returns a list
  of  all the orbits. We look at the orbit lengths and representatives for the
  orbits.
  
    Example  
    gap> orbs := Orbits( a8, pairs, OnPairs );; Length( orbs );
    2
    gap> List( orbs, Length );
    [ 8, 56 ]
    gap> List( orbs, o -> o[1] );
    [ [ 1, 1 ], [ 1, 2 ] ]
  
  
  The  action  of a8 on the first orbit (this is the one containing [1,1], try
  [1,1]  in  orbs[1])  is  of  course equivalent to the original action, so we
  ignore it and work with the second orbit.
  
    Example  
    gap> u56 := Stabilizer( a8, orbs[2][1], OnPairs );; Index( a8, u56 );
    56
  
  
  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
  [  1  ..  56 ] instead of the list of pairs. The function ActionHomomorphism
  (Reference: ActionHomomorphism) does what we need. It creates a homomorphism
  defined  on  a8  whose  image is a new group that acts on [ 1 .. 56 ] in the
  same way that a8 acts on the second orbit.
  
    Example  
    gap> h56 := ActionHomomorphism( a8, orbs[2], OnPairs );;
    gap> a8_56 := Image( h56 );;
  
  
  We  would  now like to know if the subgroup u56 of index 56 that we found is
  maximal  or  not.  As  we  have  used  already in Section 5.2, a subgroup is
  maximal  if  and  only  if  the  action  on  the  cosets of this subgroup is
  primitive.
  
    Example  
    gap> IsPrimitive( a8_56, [1..56] );
    false
  
  
  Remember  that we can leave out the function if we mean OnPoints (Reference:
  OnPoints)  but  that  we  have  to  specify the action domain for all action
  functions.
  
  We  see that a8_56 is not primitive. This means of course that the action of
  a8  on orb[2] is not primitive, because those two actions are equivalent. So
  the  stabilizer  u56  is not maximal. Let us try to find its supergroups. We
  use  the  function  Blocks  (Reference:  Blocks) to find a block system. The
  (optional)  third argument in the following example tells Blocks (Reference:
  Blocks) that we want a block system where 1 and 3 lie in one block.
  
    Example  
    gap> blocks := Blocks( a8_56, [1..56], [1,3] );;
  
  
  The  result  is  a  list of sets, such that a8_56 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 OnSets (Reference: OnSets) as third
  argument.
  
    Example  
    gap> u8_56 := Stabilizer( a8_56, blocks[1], OnSets );;
    gap> Index( a8_56, u8_56 );
    8
    gap> u8b := PreImages( h56, u8_56 );; Index( a8, u8b );
    8
    gap> IsConjugate( a8, u8, u8b );
    true
  
  
  So  we have found a supergroup of u56 that is conjugate in a8 to u8. This is
  not  surprising,  since  u8  is  a  point stabilizer, and u56 is a two point
  stabilizer in the natural action of a8 on eight points.
  
  Here  is  a  warning:  If  you  specify  OnSets (Reference: OnSets) as third
  argument to a function like Stabilizer (Reference: Stabilizers), 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 blocks[1] came from the function
  Blocks  (Reference: Blocks), which returns a list of sets, so everything was
  OK.
  
  Actually  there  is a third block system of a8_56 that gives rise to a third
  subgroup.
  
    Example  
    gap> blocks := Blocks( a8_56, [1..56], [1,13] );;
    gap> u28_56 := Stabilizer( a8_56, [1,13], OnSets );;
    gap> u28 := PreImages( h56, u28_56 );;
    gap> Index( a8, u28 );
    28
  
  
  We  know  that the subgroup u28 of index 28 is maximal, because we know that
  a8  has no subgroups of index 2, 4, or 7. However we can also quickly verify
  this by checking that a8_56 acts primitively on the 28 blocks.
  
    Example  
    gap> IsPrimitive( a8_56, blocks, OnSets );
    true
  
  
  Stabilizer (Reference: Stabilizers) is not only applicable to groups like a8
  but  also  to  their  subgroups  like  u56.  So another method to find a new
  subgroup is to compute the stabilizer of another point in u56. Note that u56
  already leaves 1 and 2 fixed.
  
    Example  
    gap> u336 := Stabilizer( u56, 3 );;
    gap> Index( a8, u336 );
    336
  
  
  Other  functions  are also applicable to subgroups. In the following we show
  that  u336  acts  regularly on the 60 triples of [ 4 .. 8 ] which contain no
  element  twice.  We construct the list of these 60 triples with the function
  Orbit  (Reference:  Orbit)  (using  OnTuples  (Reference:  OnTuples)  as the
  natural  generalization of OnPairs (Reference: OnPairs)) and then pass it as
  action domain to the function IsRegular (Reference: IsRegular). The positive
  result  of  the  regularity test means that this action is equivalent to the
  actions of u336 on its 60 elements from the right.
  
    Example  
    gap> IsRegular( u336, Orbit( u336, [4,5,6], OnTuples ), OnTuples );
    true
  
  
  Just  as  we  did  in  the  case  of  the  action on the pairs above, we now
  construct  a new permutation group that acts on [ 1 .. 336 ] in the same way
  that  a8  acts  on  the cosets of u336. But this time we let a8 operate on a
  right transversal, just like norm did in the natural homomorphism above.
  
    Example  
    gap> t := RightTransversal( a8, u336 );;
    gap> a8_336 := Action( a8, t, OnRight );;
  
  
  To find subgroups above u336 we again look for nontrivial block systems.
  
    Example  
    gap> blocks := Blocks( a8_336, [1..336] );; blocks[1];
    [ 1, 43, 85 ]
  
  
  We see that the union of u336 with its 43rd and its 85th coset is a subgroup
  in  a8_336, its index is 112. We can obtain it as the closure of u336 with a
  representative  of the 43rd coset, which can be found as the 43rd element of
  the  transversal t.  Note  that  in the representation a8_336 on 336 points,
  this subgroup corresponds to the stabilizer of the block [ 1, 43, 85 ].
  
    Example  
    gap> u112 := ClosureGroup( u336, t[43] );;
    gap> Index( a8, u112 );
    112
  
  
  Above  this  subgroup of index 112 lies a subgroup of index 56, which is not
  conjugate to u56. In fact, unlike u56 it is maximal. We obtain this subgroup
  in  the same way that we obtained u112, this time forcing two points, namely
  7 and 43 into the first block.
  
    Example  
    gap> blocks := Blocks( a8_336, [1..336], [1,7,43] );;
    gap> Length( blocks );
    56
    gap> u56b := ClosureGroup( u112, t[7] );; Index( a8, u56b );
    56
    gap> IsPrimitive( a8_336, blocks, OnSets );
    true
  
  
  We already mentioned in Section 5.2 that there is another standard action of
  permutations,  namely  the  conjugation.  E.g.,  since  no  other  action is
  specified  in  the  following  example, OrbitLength (Reference: OrbitLength)
  simply  acts via OnPoints (Reference: OnPoints), and because perm_1 ^ perm_2
  is  defined  as  the conjugation of perm_2 on perm_1, in fact we compute the
  length of the conjugacy class of (1,2)(3,4)(5,6)(7,8).
  
    Example  
    gap> OrbitLength( a8, (1,2)(3,4)(5,6)(7,8) );
    105
    gap> orb := Orbit( a8, (1,2)(3,4)(5,6)(7,8) );;
    gap> u105 := Stabilizer( a8, (1,2)(3,4)(5,6)(7,8) );; Index( a8, u105 );
    105
  
  
  Note  that  although the length of a conjugacy class of any element g in any
  finite  group  G  can  be computed as OrbitLength( G, g ), the command Size(
  ConjugacyClass( G, g ) ) is probably more efficient.
  
    Example  
    gap> Size( ConjugacyClass( a8, (1,2)(3,4)(5,6)(7,8) ) );
    105
  
  
  Of  course  the  stabilizer  u105  is in fact the centralizer of the element
  (1,2)(3,4)(5,6)(7,8).  Stabilizer  (Reference: Stabilizers) notices that and
  computes  the  stabilizer  using  the  centralizer algorithm for permutation
  groups. In the usual way we now look for the subgroups above u105.
  
    Example  
    gap> blocks := Blocks( a8, orb );; Length( blocks );
    15
    gap> blocks[1];
    [ (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) ]
  
  
  To  find  the  subgroup  of  index 15 we again use closure. Now we must be a
  little   bit   careful  to  avoid  confusion.  u105  is  the  stabilizer  of
  (1,2)(3,4)(5,6)(7,8).  We  know  that  there is a correspondence between the
  points  of  the orbit and the cosets of u105. The point (1,2)(3,4)(5,6)(7,8)
  corresponds to u105. To get the subgroup above u105 that has index 15 in a8,
  we  must  form  the  closure  of  u105  with  an  element  of the coset that
  corresponds  to  any  other point in the first block. If we choose the point
  (1,3)(2,4)(5,8)(6,7),   we   must   use   an   element   of   a8  that  maps
  (1,2)(3,4)(5,6)(7,8)      to      (1,3)(2,4)(5,8)(6,7).     The     function
  RepresentativeAction (Reference: RepresentativeAction) 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,  RepresentativeAction  (Reference:
  RepresentativeAction) returns fail.
  
    Example  
    gap> rep := RepresentativeAction( a8, (1,2)(3,4)(5,6)(7,8),
    >                                        (1,3)(2,4)(5,8)(6,7) );
    (2,3)(6,8)
    gap> u15 := ClosureGroup( u105, rep );; Index( a8, u15 );
    15
  
  
  u15  is of course a maximal subgroup, because a8 has no subgroups of index 3
  or 5.  There  is  in  fact another class of subgroups of index 15 above u105
  that we get by adding (2,3)(6,7) to u105.
  
    Example  
    gap> u15b := ClosureGroup( u105, (2,3)(6,7) );; Index( a8, u15b );
    15
    gap> RepresentativeAction( a8, u15, u15b );
    fail
  
  
  RepresentativeAction  (Reference:  RepresentativeAction) tells us that there
  is  no  element g in a8 such that u15 ^ g = u15b. Because ^ also denotes the
  conjugation of subgroups this tells us that u15 and u15b are not conjugate.
  
  Summary.  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., Cycle (Reference: Cycle) and Permutation (Reference:
  Permutation).  These  are  fully  described  in  Chapter  'Reference:  Group
  Actions'.
  
  
  5.4 Group Homomorphisms by Images
  
  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 G → H by specifying a
  generating  set  for  G  and the images of these generators in H. We use the
  function  GroupHomomorphismByImages(  G,  H,  gens,  imgs  ) where gens is a
  generating  set  for  G  and  imgs is a list whose ith entry is the image of
  gens[i] under the homomorphism.
  
    Example  
    gap> s4 := Group((1,2,3,4),(1,2));; s3 := Group((1,2,3),(1,2));;
    gap> hom := GroupHomomorphismByImages( s4, s3,
    >           GeneratorsOfGroup(s4), [(1,2),(2,3)] );
    [ (1,2,3,4), (1,2) ] -> [ (1,2), (2,3) ]
    gap> Kernel( hom );
    Group([ (1,4)(2,3), (1,3)(2,4) ])
    gap> Image( hom, (1,2,3) );
    (1,2,3)
    gap> Size( Image( hom, DerivedSubgroup(s4) ) );
    3
  
  
    Example  
    gap> PreImage( hom, (1,2,3) );
    Error, <map> must be an inj. and surj. mapping called from
    <function "PreImage">( <arguments> )
     called from read-eval loop at line 4 of *stdin*
    you can 'quit;' to quit to outer loop, or
    you can 'return;' to continue
    brk> quit;
  
  
    Example  
    gap> PreImagesRepresentative( hom, (1,2,3) );
    (1,4,2)
    gap> PreImage( hom, TrivialSubgroup(s3) );  # the kernel
    Group([ (1,4)(2,3), (1,3)(2,4) ])
  
  
  This  homomorphism  from  S_4  onto  S_3 is well known from elementary group
  theory.  Images  of  elements and subgroups under hom can be calculated with
  the  function  Image  (Reference:  Image).  But since the mapping hom is not
  bijective,  we  cannot  use  the function PreImage (Reference: PreImage) for
  preimages of elements (they can have several preimages). Instead, we have to
  use   PreImagesRepresentative  (Reference:  PreImagesRepresentative),  which
  returns  one  preimage if at least one exists (and would return fail if none
  exists,  which  cannot  occur for our surjective hom). On the other hand, we
  can  use  PreImage  (Reference:  PreImage)  for the preimage of a set (which
  always exists, even if it is empty).
  
  Suppose  we  mistype  the  input  when trying to construct a homomorphism as
  below.
  
    Example  
    gap> GroupHomomorphismByImages( s4, s3,
    >        GeneratorsOfGroup(s4), [(1,2,3),(2,3)] );
    fail
  
  
  There is no such homomorphism, hence fail is returned. But note that because
  of  this,  GroupHomomorphismByImages  (Reference: GroupHomomorphismByImages)
  must  do  some checks, and this was also done for the mapping hom above. One
  can  avoid  these checks if one is sure that the desired homomorphism really
  exists.  For  that,  the  function  GroupHomomorphismByImagesNC  (Reference:
  GroupHomomorphismByImagesNC) can be used; the NC stands for no check.
  
  But  note  that  horrible  things  can happen if GroupHomomorphismByImagesNC
  (Reference:  GroupHomomorphismByImagesNC)  is  used  when the input does not
  describe a homomorphism.
  
    Example  
    gap> hom2 := GroupHomomorphismByImagesNC( s4, s3,
    >            GeneratorsOfGroup(s4), [(1,2,3),(2,3)] );
    [ (1,2,3,4), (1,2) ] -> [ (1,2,3), (2,3) ]
    gap> Size( Kernel(hom2) );
    24
  
  
  In  other  words,  GAP  claims  that  the  kernel  is  the full s4, yet hom2
  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)).  But  if  you  use  the  command
  GroupHomomorphismByImagesNC  (Reference:  GroupHomomorphismByImagesNC),  GAP
  trusts you.
  
    Example  
    gap> IsGroupHomomorphism( hom2 );
    true
  
  
  And then it produces serious nonsense if the thing is not a homomorphism, as
  seen above!
  
  Besides    the    safe    command    GroupHomomorphismByImages   (Reference:
  GroupHomomorphismByImages), which returns fail if the requested homomorphism
  does   not   exist,   there   is  the  function  GroupGeneralMappingByImages
  (Reference:  GroupGeneralMappingByImages),  which  returns a general mapping
  (that  is,  a  possibly  multi-valued  mapping)  that  can  be  tested  with
  IsGroupHomomorphism (Reference: IsGroupHomomorphism).
  
    Example  
    gap> hom2 := GroupGeneralMappingByImages( s4, s3,
    >            GeneratorsOfGroup(s4), [(1,2,3),(2,3)] );;
    gap> IsGroupHomomorphism( hom2 );
    false
  
  
  But  the  possibility  of  testing  for being a homomorphism is not the only
  reason  why  GAP  offers  group  general mappings. Another (more important?)
  reason  is  that their existence allows reversal of arrows in a homomorphism
  such  as  our  original  hom.  By this we mean the GroupHomomorphismByImages
  (Reference:  GroupHomomorphismByImages) with left and right sides exchanged,
  in   which  case  it  is  of  course  merely  a  GroupGeneralMappingByImages
  (Reference: GroupGeneralMappingByImages).
  
    Example  
    gap> rev := GroupGeneralMappingByImages( s3, s4,
    >           [(1,2),(2,3)], GeneratorsOfGroup(s4) );;
  
  
  Now  hom  maps a to b if and only if rev maps b to a, for a ∈ s4 and b ∈ s3.
  Since  every  such  b  has  four preimages under hom, it now has four images
  under  rev. Just as the four preimages form a coset of the kernel V_4 ≤s4 of
  hom,  they  also  form  a coset of the cokernel V_4 ≤s4 of rev. The cokernel
  itself  is  the  set of all images of One( s3 ). (It is a normal subgroup in
  the  group  of  all  images  under  rev.) The operation One (Reference: One)
  returns  the  identity  element  of  a  group.  And this is why GAP wants to
  perform   such  a  reversal  of  arrows:  it  calculates  the  kernel  of  a
  homomorphism  like hom as the cokernel of the reversed group general mapping
  (here rev).
  
    Example  
    gap> CoKernel( rev );
    Group([ (1,4)(2,3), (1,3)(2,4) ])
  
  
  The  reason  why  rev  is not a homomorphism is that it is not single-valued
  (because hom 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). GAP requires that a group homomorphism be both single-valued and
  total,  so  you  will  get  fail if you say GroupHomomorphismByImages( G, H,
  gens,  imgs  )  where  gens  does  not generate G (even if this would give a
  decent  homomorphism  on  the  subgroup  generated  by  gens).  For  a  full
  description, see Chapter 'Reference: Group Homomorphisms'.
  
  The  last  example  of  this  section  shows  that  the notion of kernel and
  cokernel  naturally  extends  even  to  the  case where neither hom2 nor its
  inverse general mapping (with arrows reversed) is a homomorphism.
  
    Example  
    gap> CoKernel( hom2 );  Kernel( hom2 );
    Group([ (2,3), (1,3) ])
    Group([ (3,4), (2,3,4), (1,2,4) ])
    gap> IsGroupHomomorphism( InverseGeneralMapping( hom2 ) );
    false
  
  
  Summary.  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).
  
  
  5.5 Nice Monomorphisms
  
  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.
  
  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:
  
    Example  
    gap> grp:=GL(2,3);;
    gap> dom:=GF(3)^2;;
    gap> hom := ActionHomomorphism( grp, dom );; IsInjective( hom );
    true
    gap> p := Image( hom,grp );
    Group([ (4,7)(5,8)(6,9), (2,7,6)(3,4,8) ])
  
  
  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 hom. Lifting back a conjugacy class means finding the
  preimage  of the representative and of the centralizer; the latter is called
  StabilizerOfExternalSet (Reference: StabilizerOfExternalSet) in GAP (because
  conjugacy  classes are represented as external sets, see Section 'Reference:
  Conjugacy Classes').
  
    Example  
    gap> pcls := ConjugacyClasses( p );; gcls := [  ];;
    gap> for pc  in pcls  do
    >      gc:=ConjugacyClass(grp,
    >                   PreImagesRepresentative(hom,Representative(pc)));
    >      SetStabilizerOfExternalSet(gc,PreImage(hom,
    >                                      StabilizerOfExternalSet(pc)));
    >      Add( gcls, gc );
    >    od;
    gap> List( gcls, Size );
    [ 1, 8, 12, 1, 8, 6, 6, 6 ]
  
  
  All  the  steps we have made above are automatically performed by GAP if you
  simply ask for ConjugacyClasses( grp ), provided that GAP already knows that
  grp  is  finite (e.g., because you asked IsFinite( grp ) before). The reason
  for  this  is  that  a  finite  matrix  group  like grp is handled by a nice
  monomorphism.  For  such  groups,  GAP  uses  the  command  NiceMonomorphism
  (Reference:  NiceMonomorphism)  to construct a monomorphism (such as the hom
  in the previous example) and then proceeds as we have done above.
  
    Example  
    gap> grp:=GL(2,3);;
    gap> IsHandledByNiceMonomorphism( grp );
    true
    gap> hom := NiceMonomorphism( grp );
    <action isomorphism>
    gap> p :=Image(hom,grp);
    Group([ (4,7)(5,8)(6,9), (2,7,6)(3,4,8) ])
    gap> cc := ConjugacyClasses( grp );; ForAll(cc, x-> x in gcls); 
    true
    gap> ForAll(gcls, x->x in cc); # cc and gcls might be ordered differently
    true
  
  
  Note  that  a  nice monomorphism might be defined on a larger group than grp
  –so we have to use Image( hom, grp ) and not only Image( hom ).
  
  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.
  
    Example  
    gap> p:=Group((1,7,6,8)(2,5,3,4), (1,2,6,3)(4,8,5,7));;
    gap> aut := AutomorphismGroup( p );; NiceMonomorphism(aut);;
    gap> niceaut := NiceObject( aut );
    Group([ (1,4,2,3), (1,5,4)(2,6,3), (1,2)(3,4), (3,4)(5,6) ])
    gap> IsomorphismGroups( niceaut, SymmetricGroup( 4 ) );
    [ (1,4,2,3), (1,5,4)(2,6,3), (1,2)(3,4), (3,4)(5,6) ] -> 
    [ (1,4,3,2), (1,3,2), (1,3)(2,4), (1,2)(3,4) ]
  
  
  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
  NiceMonomorphism (Reference: NiceMonomorphism)), 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 NiceMonomorphism
  (Reference:  NiceMonomorphism),  because  a newly-constructed group will not
  yet have a NiceMonomorphism (Reference: NiceMonomorphism) set.
  
    Example  
    gap> nicer := NiceMonomorphism(aut) * IsomorphismPcGroup(niceaut);;
    gap> aut2 := GroupByGenerators( GeneratorsOfGroup( aut ) );;
    gap> SetIsHandledByNiceMonomorphism( aut2, true );
    gap> SetNiceMonomorphism( aut2, nicer );
    gap> NiceObject( aut2 );  # a pc group
    Group([ f1*f2, f2^2*f3, f4, f3 ])
  
  
  The star * denotes composition of mappings from the left to the right, as we
  have seen in Section 5.2 above. Reconstructing the automorphism group may of
  course  result  in  the  loss of other information GAP had already gathered,
  besides the (not-so-)nice monomorphism.
  
  Summary.  In  this  section  we  have seen how calculations in groups can be
  carried  out  in  isomorphic  images  in nicer groups. We have seen that GAP
  pursues  this  technique  automatically for certain classes of groups, e.g.,
  for matrix groups that are known to be finite.
  
  
  5.6 Further Information about Groups and Homomorphisms
  
  Groups  and  the  functions  for  groups  are treated in Chapter 'Reference:
  Groups'.  There  are  several  chapters  dealing  with  groups  in  specific
  representations,  for  example  Chapter 'Reference:  Permutation  Groups' on
  permutation  groups, 'Reference: Polycyclic Groups' on polycyclic (including
  finite  solvable)  groups,  'Reference:  Matrix Groups' on matrix groups and
  'Reference:   Finitely  Presented  Groups'  on  finitely  presented  groups.
  Chapter 'Reference:   Group   Actions'   deals  with  group  actions.  Group
  homomorphisms are the subject of Chapter 'Reference: Group Homomorphisms'.