GAP

Main Branches

Downloads  Installation  Overview  Data Libraries  Packages  Documentation  Contacts  FAQ  GAP 3 
This is a page on GAP 3, which is still available, but no longer supported. The present version is GAP 4  (See  Status of GAP 3).

Constructing the Higman-Sims Group from the Number 23

See also the  GAP 4 page on the construction of HS and Co3.


This is an example presented by Alexander Hulpke in the software demonstration at the 16th British Combinatorial Conference in London, July 1997.

The associated GAP 3 input file is also available.


GAP 3 Demonstration at BCC 16

This is - slightly edited - the example I gave in my demonstration at the sixteenth British Combinatorial Conference in London. I hope it can be of use to some people.

The audience consisted mainly of combinatorialists, thus the exaple is biased rather heavily towards graph and coding theory.

In this example, I want to construct the Higman-Sims group, starting with the number 23. It shows, how easy it is in GAP to have different areas of mathematics interacting. It also indicates to which extent theoretical constructions can be made explicit using current day computer algebra software.

Take for example the indeterminate over the field with two elements.
  gap> SizeScreen([61, ]);;
  gap> x:=Indeterminate(GF(2));
  X(GF(2))
Assigning a name tag to the indeterminate will make it be printed more nicely
  gap> x.name:="x";;
Now we really start. We construct a small degree polynomial, factorize it and take one of the nontrivial factors.
  gap> f:=x^23-1;
  Z(2)^0*(x^23 + 1)
  gap> Factors(f);
  [ Z(2)^0*(x + 1), Z(2)^0*(x^11 + x^10 + x^6 + x^5 + x^
      4 + x^2 + 1), Z(2)^0*(x^11 + x^9 + x^7 + x^6 + x^
      5 + x + 1) ]
  gap> f:=First(Factors(f),i->Degree(i)>1);
  Z(2)^0*(x^11 + x^10 + x^6 + x^5 + x^4 + x^2 + 1)
To form a cyclic code from this polynomial, we load the coding theory package GUAVA:
  gap> SizeScreen([72, ]);;
  gap> RequirePackage("guava");
  
                ___________                   |                  
               /            \           /   --+--  Version 1.3   
              /      |    | |\\        //|    |                  
             |    _  |    | | \\      // |                        
             |     \ |    | |--\\    //--|     Jasper Cramwinckel  
              \     ||    | |   \\  //   |     Erik Roijackers     
               \___/  \___/ |    \\//    |     Reinald Baart       
                                               Eric Minkes       
Now we form the corresponding code over GF(2) in 23 dimensions.
  gap> cod:=GeneratorPolCode(f,23,GF(2));
  a cyclic [23,12,1..7]3 code defined by generator polynomial over GF(2)
Guava permits us to compute a lot of properties of the code, for example, we can check that it is perfect.
  gap> IsPerfectCode(cod);
  true
In fact, our code is the famous binary Golay code. If we extend it by a parity bit, we get the extended Golay code. We also glance shortly at the numbers of the weight distribution, that GUAVA can compute for us.
  gap> ext:=ExtendedCode(cod);
  a linear [24,12,8]4 extended code
  gap> SizeScreen([61, ]);;
  gap> WeightDistribution(ext);
  [ 1, 0, 0, 0, 0, 0, 0, 0, 759, 0, 0, 0, 2576, 0, 0, 0, 
    759, 0, 0, 0, 0, 0, 0, 0, 1 ]
The automorphism group of this code is the Mathieu group M24. (GUAVA calls the external code automorphism group program by Jeff Leon for this computation.) We check the size of the obtained group.
  gap> m24:=AutomorphismGroup(ext);
  Group( ( 1, 2)( 6,15,24,18)( 7,14,12,19)( 9,17,16,20)
  (10,21,23,22)(11,13), ( 2, 3)( 6,10)( 7,24)( 9,17)(11,13)
  (12,18)(14,21)(15,23), ( 3, 4)( 7,19)(10,22)(11,13)(12,14)
  (15,18)(17,20)(21,23), ( 4, 5)( 6,23,21,16)( 7, 9,20,10)
  (11,13)(12,15,17,19)(14,22,18,24), ( 5, 9,11,17)
  ( 6,19,24,21)( 7,23)( 8,20,13,16)(10,12)(14,15,22,18), 
  ( 5, 8)( 7,23)( 9,16)(10,12)(11,13)(14,22)(17,20)(19,21), 
  ( 6,10,19)( 7,14,18)( 8,11,13)( 9,17,16)(12,21,24)
  (15,23,22), ( 6,19)( 7, 9)(10,20)(12,16)(14,24)(15,21)
  (17,23)(18,22), ( 6, 7)( 9,19)(10,15)(12,24)(14,16)(17,22)
  (18,23)(20,21), ( 6,18)( 7,23)( 9,17)(10,12)(14,21)(15,24)
  (16,20)(19,22), ( 6,15)( 7,10)( 9,20)(12,23)(14,22)(16,17)
  (18,24)(19,21) )
  gap> m24.name:="m24";;
  gap> Size(m24);
  244823040
M22.2 is a duad (=set of size 2) stabilizer in M24, its action on the 22 complementary points is faithful.
  gap> m22a:=Stabilizer(m24,[23,24],OnSets);
  Subgroup( m24, 
  [ ( 1, 3)( 5,17)( 6,18)( 7,10)( 8,16)( 9,13)(11,20)(21,22),
    ( 3, 4)( 5,13)( 6,15)( 7,10)( 9,21)(14,16)(17,22)(19,20),
    ( 1, 2)( 6,15)( 7,10)( 8,11)( 9,19)(14,17)(16,22)(20,21),
    ( 4,16)( 6,21)( 7,19)( 8,12)( 9,20)(10,15)(11,18)(13,22),
    ( 1, 2)( 6, 7)( 8,11)( 9,20)(10,15)(12,18)(19,21)(23,24) 
   ] )
  gap> m22a:=Operation(m22a,[1..22]);
  Group( ( 1, 3)( 5,17)( 6,18)( 7,10)( 8,16)( 9,13)(11,20)
  (21,22), ( 3, 4)( 5,13)( 6,15)( 7,10)( 9,21)(14,16)(17,22)
  (19,20), ( 1, 2)( 6,15)( 7,10)( 8,11)( 9,19)(14,17)(16,22)
  (20,21), ( 4,16)( 6,21)( 7,19)( 8,12)( 9,20)(10,15)(11,18)
  (13,22), ( 1, 2)( 6, 7)( 8,11)( 9,20)(10,15)(12,18)
  (19,21) )
Our next step will be to construct the Higman-Sims graph. The ATLAS tells us on page 80 that this is a rank 3 graph of valence 22 on 100 points, the point stabilizer in the automorphism group beging M22.2. This group then acts on 22+77 points. For our construction, we next need the action of M22.2 on 77 points. We will get it by acting on the cosets of a suitable subgroup. To get it, we use the classification of maximal subgroups given in the ATLAS:
  Order   Index  Structure  G.2       Abstract   Mathieu
   5760      77  2^4:A_6    2^4:S_6   N(2A^4)    hexad
This tells us:
  • The permutation representation of M22 extends to M22.2,
  • The point stabilizer in this action is a subgroup of type 2^4:S_6, so it contains an elementary abelian normal subgroup of size 16.
  • It has index 77, so it contains a full 2-Sylow subgroup. Thus we can find the 2^4 as a normal subgroup of a 2-Sylow subgroup
We compute a 2-sylow subgroup and convert it to an AgGroup. This is a special representation for solvable groups in which computations go quicker.
  gap> s:=SylowSubgroup(m22a,2);;
  gap> a:=AgGroup(s);
  Group( g1, g2, g3, g4, g5, g6, g7, g8 )
We compute all elementary abelian normal subgroups of size 16 in this group.
  gap> n:=Filtered(NormalSubgroups(a),
  > i->Size(i)=16 and IsElementaryAbelian(i));
  [ Subgroup( Group( g1, g2, g3, g4, g5, g6, g7, g8 ), 
      [ g1, g3, g6*g7, g8 ] ), 
    Subgroup( Group( g1, g2, g3, g4, g5, g6, g7, g8 ), 
      [ g2, g3, g6*g7, g8 ] ), 
    Subgroup( Group( g1, g2, g3, g4, g5, g6, g7, g8 ), 
      [ g2, g6, g7, g8 ] ), Subgroup( Group( g1, g2, g3, g4, 
      g5, g6, g7, g8 ), [ g1*g2, g3, g6*g7, g8 ] ), 
    Subgroup( Group( g1, g2, g3, g4, g5, g6, g7, g8 ), 
      [ g5, g6, g7, g8 ] ) ]
The component a.bijection is an homomorphism back into the permutation group. We use it to get these subgroups as permutation groups.
  gap> n:=List(n,i->Image(a.bijection,i));;
We now could just look at the sizes of the normalizers to pick the right group. I happen to know, however, that the 2^4 is regular. (The remaining 6 points form the hexad stabilized by the normalizer.) We pick the right group and compute its normalizer.
  gap> u:=First(n,i->IsRegular(i,PermGroupOps.MovedPoints(i)));;
  gap> un:=Normalizer(m22a,u);;
Now we compute the action on the cosets.
  gap> mop:=Operation(m22a,RightCosets(m22a,un),OnRight);;
(It is worthwile to mention, that the following command
  mop:=Operation(m22a,CanonicalRightTransversal(m22a,un),
	  OnCanonicalCosetElements(m22a,un));;
produces essentially the same result, but usually much quicker.)

The corresponding operation homomorphism is the link between both permutation representations.

  gap> ophom:=OperationHomomorphism(m22a,mop);;
To get the simultaneous action on 22 and 77 points, we form the direct product of the group on 22 and on 77 points and take the diagonal subgroup. We get it from both embeddings into the direct product by multiplying the images of the generators under both embeddings.
  gap> dp:=DirectProduct(m22a,mop);;
  gap> emb1:=Embedding(m22a,dp,1);;
  gap> emb2:=Embedding(mop,dp,2);;
  gap> diag:=List(m22a.generators,
  > i->Image(emb1,i)*Image(emb2,Image(ophom,i)));;
We take the group generated by these diagonal elements and give it a name. (Note that we have to give the identity here, as diag is a list which could be empty.)
  gap> diag:=Group(diag,());;
  gap> diag.name:="M22.2-diag";;
It is now time to construct the graph. For this we use the GRAPE share package.
  gap> SizeScreen([67, ]);;
  gap> RequirePackage("grape");
  
  Loading  GRAPE 2.31  (GRaph Algorithms using PErmutation groups),
  by L.H.Soicher@qmw.ac.uk.
  
  gap> SizeScreen([61, ]);;
GRAPE permits us to construct the graph by adjoining one edge after another. As we already know, that M22.2 in the diagonal action is a subgroup of the automorphism group, we can tell this to GRAPE and need to adjoin only one edge from every orbit of the group.
  gap> gamma:=NullGraph(diag,100);
  rec(
    isGraph := true,
    order := 100,
    group := M22.2-diag,
    schreierVector := 
     [ -1, 3, 1, 2, 1, 4, 5, 1, 2, 4, 3, 4, 4, 2, 2, 4, 3, 
        4, 5, 1, 1, 3, -2, 5, 4, 1, 5, 5, 4, 2, 4, 4, 3, 4, 
        4, 2, 3, 4, 1, 4, 5, 1, 4, 2, 2, 3, 1, 5, 1, 5, 4, 
        2, 2, 2, 5, 2, 5, 3, 3, 4, 5, 3, 5, 2, 5, 3, 3, 1, 
        3, 4, 1, 3, 1, 1, 1, 4, 1, 4, 3, 5, 5, 5, 3, 3, 3, 
        1, 2, 4, 4, 4, 2, 2, 2, 4, 1, 1, 1, 1, 2, -3 ],
    adjacencies := [ [  ], [  ], [  ] ],
    representatives := [ 1, 23, 100 ],
    isSimple := true )
Graphs in GRAPE are digraphs, so we have to add each edge in both directions. The first edge is to connect the 22 points with point 100 to make up for valence 22:
  gap> AddEdgeOrbit(gamma,[1,100]);AddEdgeOrbit(gamma,[100,1]);
The ATLAS further tells us:
"each of the remeining 77 vertices is joined to 6 of these [the 22] points, and may be labelled by the corresponding hexad".

So we get a hexad in the first 22 points (remember, it is an orbit of the subgroup we got as point stabilizer for the action on 77 points) and add edges to the second orbit. (As M22.2 is transitive on this second orbit, it is sufficient to consider one point there.)

  gap> hexad:=First(Orbits(un,[1..22]),i->Length(i)=6);
  [ 1, 13, 15, 18, 17, 19 ]
  gap> hexad:=Set(hexad);
  [ 1, 13, 15, 17, 18, 19 ]
  gap> for i in hexad do AddEdgeOrbit(gamma,[i,23]);
  > AddEdgeOrbit(gamma,[23,i]);
  > od;
Looking at the neighbourhood of 23 we see that we have not yet reached valence 22.
  gap> Adjacency(gamma,23);
  [ 1, 13, 15, 17, 18, 19 ]
Indeed, we still have to consider the next rule, to determine which vertices in the second orbit are joined to vertex 23:
"Two of these 77 vertices are joined just if the corresponding hexads are disjoint." Using again the acting group we see that it is sufficient to test jointness for representatives of the orbits of the stabilizer of 23. We compute this stabilizer and determine orbit representatives:
  gap> stab:=Stabilizer(diag,23);;
  gap> storbrep:=List(Orbits(stab,[23..99]),i->i[1]);
  [ 23, 24, 43 ]
To get the corresponding hexads, we simply search for elements from the acting group diag which map 23 to these representatives. Mapping the hexad corresponding to 23 with these elements yields the corresponding hexads. We compute these images and look at their intersections with the original hexad.
  gap> reps:=List(storbrep,i->RepresentativeOperation(diag,23,i));
  [ (), ( 6,10)( 7,15)( 9,21)(12,18)(14,17)(16,22)(19,20)
      (23,24)(26,31)(27,35)(28,30)(29,38)(34,36)(39,41)
      (42,44)(45,50)(46,48)(47,49)(52,61)(54,59)(55,60)
      (57,62)(63,64)(65,67)(66,68)(70,74)(71,73)(75,76)
      (79,80)(81,84)(82,83)(86,89)(87,90)(91,92)(95,97), 
    ( 1,16,12, 8,14, 4, 3)( 5,13, 6,11, 7,19, 9)
      (10,15,21,17,22,20,18)(23,43,34,39,33,42,76)
      (24,46,71,58,66,60,77)(25,48,67,55,74,64,62)
      (26,45,73,35,37,40,52)(27,44,65,57,59,78,69)
      (28,41,61,56,70,72,63)(29,32,49,53,54,68,30)
      (31,38,47,36,50,75,51)(79,88,93,95,87,82,85)
      (80,81,90,86,91,97,83)(84,89,94,99,98,92,96) ]
  gap> repi:=List(reps,i->Intersection(hexad,OnSets(hexad,i)));
  [ [ 1, 13, 15, 17, 18, 19 ], [ 1, 13 ], [  ] ]
Only in one case the hexads intersect trivially. We get the position and add the respective edges:
  gap> pos:=First([1..3],i->Length(repi[i])=0);
  3
  gap> AddEdgeOrbit(gamma,[23,storbrep[pos]]);
  gap> AddEdgeOrbit(gamma,[storbrep[pos],23]);
Now the graph is completed. We check that it is indeed a simple graph, look at the adjecency of 23 and find out it is distance regular.
  gap> IsSimpleGraph(gamma);
  true
  gap> Adjacency(gamma,23);
  [ 1, 13, 15, 17, 18, 19, 43, 44, 47, 48, 59, 61, 70, 71, 
    76, 77, 82, 84, 88, 90, 92, 94 ]
  gap> IsDistanceRegular(gamma);
  true
Finally, we compute the automorphism group of the graph. This is done by calling Brendan McKays `nauty' program, though we don't see anything from this.
  gap> aug:=AutGroupGraph(gamma);;
Indeed the size is correct for HS.2. We can ensure this by looking at the composition series:
  gap> Size(aug);
  88704000
  gap> DisplayCompositionSeries(aug);
  <G> (3 gens, size 88704000)
   | Z(2)
  <S> (2 gens, size 44352000)
   | HS
  <1> (0 gens)
We now could get HS as the derived subgroup and continue to work with it. This example session, however is finished here.
  gap> quit;

July 17, 1997

Alexander Hulpke
Department of Mathematics
Colorado State University
Weber Building
Fort Collins, CO 80523
USA
email: hulpke@math.colostate.edu