How do I construct … in GAP?

This page is devoted to answering some basic questions along the line
“How do I construct … in GAP?” You may view the html source code
for the GAP commands without the output or GAP prompt.

Please send suggestions, additions, corrections to
David Joyner.

This page itself is under construction…


Questions

How
do I construct a … group?

permutation
dihedral 
cyclicconjugacy classes of a
finitely presented

How
do I … a polynomial?
How do I find the … of a group
representation?
How
do I compute an mod m, where A is …?
Given
a group G, how do I compute … ?

Answers


    • permutation:
      To construct a permutation group, write down generators in disjoint cycle notation,
      put them in a list (i.e., surround them by square brackets), andThe permutation group G generated by the cycles
      (1,2)(3,4) and (1,2,3):
gap> G:=Group((1,2)(3,4),(1,2,3));

Group([ (1,2)(3,4), (1,2,3) ])

This is of course a subgroup of the symmetric group S4 on 4
letters.
Indeed, this G is in fact the alternating group
on four letters, A4.

By virtue of the fact that the permutations generating G employ
integers less than or equal to 4, this group G
is a subgroup of the symmetric group S4 on 4
letters. Some permutation groups have special constructions:

gap> S4:=SymmetricGroup(4);
Sym( [ 1 .. 4 ] )
gap> A4:=AlternatingGroup(4);
Alt( [ 1 .. 4 ] )
gap> IsSubgroup(S4,G);
true
gap> IsSubgroup(A4,G);
true
gap> S3:=SymmetricGroup(3);
Sym( [ 1 .. 3 ] )
gap> IsSubgroup(S3,G);
false


    • dihedral
      To construct a dihedral group, use the special “DihedralGroup” command:
gap> G:=DihedralGroup(6);

gap> Size(G);
6
gap> f:=GeneratorsOfGroup( G );
[ f1, f2 ]
gap> f[1]^2; f[2]^3;
identity of ...
identity of ...
gap> f[1]^2= f[2]^3;
true


  • cyclic group
    To construct a cyclic group, you may
    construct integers mod n:

    gap> R:=ZmodnZ( 12);
    (Integers mod 12)
    gap> a:=Random(R);
    ZmodnZObj( 11, 12 )
    gap> 4*a;
    ZmodnZObj( 8, 12 )
    gap> b:=Random(R);
    ZmodnZObj( 9, 12 )
    gap> a+b;
    ZmodnZObj( 8, 12 )
    

    or use the special “CyclicGroup” command

    gap> G:=CyclicGroup(12);
    pc group of size 12 with 3 generators
    gap> a:=Random(G);
    f3^2
    gap> f:=GeneratorsOfGroup( G );
    [ f1, f2, f3 ]
    gap> f[1]^4;
    f3
    gap> f[1]^12;
    identity of ...
    
    


  • conjugacy:
    The conjugacy classes of a group G are computed using
    the “ConjugacyClasses” command. This is a list
    of classes{x^-1*g*x | x in G}.

    gap> G:=SL(2,7);
    SL(2,7)
    gap> CG:=ConjugacyClasses(G);
    [ [ [ Z(7)^0, 0*Z(7) ], [ 0*Z(7), Z(7)^0 ] ]^G,
      [ [ 0*Z(7), Z(7)^3 ], [ Z(7)^0, Z(7)^5 ] ]^G,
      [ [ 0*Z(7), Z(7)^4 ], [ Z(7)^5, Z(7)^5 ] ]^G,
      [ [ Z(7)^3, 0*Z(7) ], [ 0*Z(7), Z(7)^3 ] ]^G,
      [ [ 0*Z(7), Z(7)^3 ], [ Z(7)^0, Z(7)^2 ] ]^G,
      [ [ 0*Z(7), Z(7)^4 ], [ Z(7)^5, Z(7)^2 ] ]^G,
      [ [ 0*Z(7), Z(7)^3 ], [ Z(7)^0, 0*Z(7) ] ]^G,
      [ [ 0*Z(7), Z(7)^3 ], [ Z(7)^0, Z(7)^4 ] ]^G,
      [ [ 0*Z(7), Z(7)^3 ], [ Z(7)^0, Z(7) ] ]^G,
      [ [ Z(7)^4, 0*Z(7) ], [ 0*Z(7), Z(7)^2 ] ]^G,
      [ [ Z(7)^5, 0*Z(7) ], [ 0*Z(7), Z(7) ] ]^G ]
    gap> g:=Representative(CG[3]); Order(g);
    [ [ 0*Z(7), Z(7)^4 ], [ Z(7)^5, Z(7)^5 ] ]
    14
    gap> g:=Representative(CG[4]); Order(g);
    [ [ Z(7)^3, 0*Z(7) ], [ 0*Z(7), Z(7)^3 ] ]
    2
    gap> g:=Representative(CG[5]); Order(g);
    [ [ 0*Z(7), Z(7)^3 ], [ Z(7)^0, Z(7)^2 ] ]
    7
    gap> g:=Representative(CG[6]); Order(g);
    [ [ 0*Z(7), Z(7)^4 ], [ Z(7)^5, Z(7)^2 ] ]
    7
    gap>                            
    


  • presented
    To construct a finitely presented group in GAP, use the
    “FreeGroup” and “” commands. Here is one example.

    gap> M12 := MathieuGroup( 12 );
    Group([ (1,2,3,4,5,6,7,8,9,10,11), (3,7,11,8)(4,10,5,6), (1,12)(2,11)(3,6)(4,8)(5,9)(7,10) ])
    gap> F := FreeGroup( "a", "b", "c" );
    free group on the generators [ a, b, c ]
    gap> words := [ F.1, F.2 ];
    [ a, b ]
    gap> P := PresentationViaCosetTable( M12, F, words );
    presentation with 3 gens and 10 rels of total length 97
    gap> TzPrintRelators( P );
    #I  1. c^2
    #I  2. b^4
    #I  3. a*c*a*c*a*c
    #I  4. a*b^2*a*b^-2*a*b^-2
    #I  5. a^11
    #I  6. a^2*b*a^-2*b^2*a*b^-1*a^2*b^-1
    #I  7. a*b*a^-1*b*a^-1*b^-1*a*b*a^-1*b*a^-1*b^-1
    #I  8. a^2*b*a^2*b^2*a^-1*b*a^-1*b^-1*a^-1*b^-1
    #I  9. a*b*a*b*a^2*b^-1*a^-1*b^-1*a*c*b*c
    #I  10. a^4*b*a^2*b*a^-2*c*a*b*a^-1*c
    gap> G := FpGroupPresentation( P );
    fp group on the generators [ a, b, c ]
    gap> RelatorsOfFpGroup( G );  
    [ c^2, b^4, a*c*a*c*a*c, a*b^-2*a*b^-2*a*b^-2, a^11, a^2*b*a^-2*b^-2*a*b^-1*a^2*b^-1, a*b*a^-1*b*a^-1*b^-1*a*b*a^-1*b*a^-1*b^-1,
      a^2*b*a^2*b^-2*a^-1*b*a^-1*b^-1*a^-1*b^-1, a*b*a*b*a^2*b^-1*a^-1*b^-1*a*c*b*c, a^4*b*a^2*b*a^-2*c*a*b*a^-1*c ]
    gap> Size(M12);
    95040
    gap> Size(G);
    95040
    gap> IsomorphismGroups(G,M12); 
    ????????
    

    The last command is computationally intensive and requires more
    than the default memory allocation of 256M of RAM.

    Here is another example.

    gap> F := FreeGroup( "a", "b");
    free group on the generators [ a, b ]
    gap> G:=F/[F.1^2,F.2^3,F.1*F.2*F.1^(-1)*F.2^(-1)];
    fp group on the generators [ a, b ]
    gap> Size(G);
    6
    
    


  • rref
    The key command for row reduction is “TriangulizeMat”.
    The following example illustrates the syntax.

    gap> M:=[[1,2,3,4,5],[1,2,1,2,1],[1,1,0,0,0]];
    [ [ 1, 2, 3, 4, 5 ], [ 1, 2, 1, 2, 1 ], [ 1, 1, 0, 0, 0 ] ]
    gap> TriangulizeMat(M);
    gap> M;
    [ [ 1, 0, 0, -1, 1 ], [ 0, 1, 0, 1, -1 ], [ 0, 0, 1, 1, 2 ] ]
    gap> Display(M);
    [ [   1,   0,   0,  -1,   1 ],
      [   0,   1,   0,   1,  -1 ],
      [   0,   0,   1,   1,   2 ] ]
    gap> M:=Z(3)^0*[[1,2,3,4,5],[1,2,1,2,1],[1,1,0,0,0]];
    [ [ Z(3)^0, Z(3), 0*Z(3), Z(3)^0, Z(3) ],
      [ Z(3)^0, Z(3), Z(3)^0, Z(3), Z(3)^0 ],
      [ Z(3)^0, Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3) ] ]
    gap> TriangulizeMat(M);
    gap> Display(M);
     1 . . 2 1
     . 1 . 1 2
     . . 1 1 2
    gap>
    


  • kernel:
    There are different methods for matrices over the integers and
    matrices over a field.For integer entries, related commands include
    “NullspaceIntMat” and “SolutionNullspaceIntMat”
    in section

    25.1 “Linear equations over the integers and Integral Matrices”

    of the reference manual.

    gap> M:=[[1,2,3],[4,5,6],[7,8,9]];
    [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ]
    gap> NullspaceIntMat(M);
    [ [ 1, -2, 1 ] ]
    gap> SolutionNullspaceIntMat(M,[0,0,1]);
    [ fail, [ [ 1, -2, 1 ] ] ]
    gap> SolutionNullspaceIntMat(M,[0,0,0]);
    [ [ 0, 0, 0 ], [ [ 1, -2, 1 ] ] ]
    gap> SolutionNullspaceIntMat(M,[1,2,3]);
    [ [ 1, 0, 0 ], [ [ 1, -2, 1 ] ] ]
    
    

    Here (0,0,1) is not in the image of M
    (under v-> v*M) but (0,0,0) and (1,2,3) are.

    For field entries, related commands include
    “NullspaceMat” and “TriangulizedNullspaceMat”
    in section

    24.6 “Matrices Representing Linear Equations and the Gaussian Algorithm”

    of the reference manual.

    gap> M:=[[1,2,3],[4,5,6],[7,8,9]];
    [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ]
    gap> NullspaceMat(M);
    [ [ 1, -2, 1 ] ]
    gap> TriangulizedNullspaceMat(M);
    [ [ 1, -2, 1 ] ]
    gap> M:=[[1,2,3,1,1],[4,5,6,1,1],[7,8,9,1,1],[1,2,3,1,1]];
    [ [ 1, 2, 3, 1, 1 ], [ 4, 5, 6, 1, 1 ], [ 7, 8, 9, 1, 1 ], 
      [ 1, 2, 3, 1, 1 ] ]
    gap> NullspaceMat(M);
    [ [ 1, -2, 1, 0 ], [ -1, 0, 0, 1 ] ]
    gap> TriangulizedNullspaceMat(M);
    [ [ 1, 0, 0, -1 ], [ 0, 1, -1/2, -1/2 ] ]
    
    
    


  • characteristic polynomial:
    Please see section
    24.12.1 of the GAP reference manual
    for examples of characteristic polynomial of a
    square matrix (“CharacteristicPolynomial”) and
    section

    56.3
    for examples of the “characteristic polynomial”
    (called a “TracePolynomial”) of an
    element of a field extension.


  • character:
    GAP contains very extensive character theoretic functions
    and data libraries (including an interface the character table in the
    Atlas).
    Here is just one simple example.

    gap> G:=Group((1,2)(3,4),(1,2,3));
    Group([ (1,2)(3,4), (1,2,3) ])
    gap> T:=CharacterTable(G);
    CharacterTable( Alt( [ 1 .. 4 ] ) )
    gap> Display(T);
    CT1
    
         2  2  2  .  .
         3  1  .  1  1
    
           1a 2a 3a 3b
        2P 1a 1a 3b 3a
        3P 1a 2a 1a 1a
    
    X.1     1  1  1  1
    X.2     1  1  A /A
    X.3     1  1 /A  A
    X.4     3 -1  .  .
    
    A = E(3)^2
      = (-1-ER(-3))/2 = -1-b3
    gap> irr:=Irr(G);
    [ Character( CharacterTable( Alt( [ 1 .. 4 ] ) ), [ 1, 1, 1, 1 ] ),
      Character( CharacterTable( Alt( [ 1 .. 4 ] ) ), [ 1, 1, E(3)^2, E(3) ] ),
      Character( CharacterTable( Alt( [ 1 .. 4 ] ) ), [ 1, 1, E(3), E(3)^2 ] ),
      Character( CharacterTable( Alt( [ 1 .. 4 ] ) ), [ 3, -1, 0, 0 ] ) ]
    gap> Display(irr);
    [ [       1,       1,       1,       1 ],
      [       1,       1,  E(3)^2,    E(3) ],
      [       1,       1,    E(3),  E(3)^2 ],
      [       3,      -1,       0,       0 ] ]
    gap> chi:=irr[2]; gamma:=CG[3]; g:=Representative(gamma); g^chi;
    Character( CharacterTable( Alt( [ 1 .. 4 ] ) ), [ 1, 1, E(3)^2, E(3) ] )
    (1,2,3)^G
    (1,2,3)
    E(3)^2
    
    

    For further details and examples, see chapters
    69
    72 of the
    GAP reference manual.

  • brauer:
    Just a simple example of what GAP can do here.
    To construct a Brauer character table:

    gap> G:=Group((1,2)(3,4),(1,2,3));
    Group([ (1,2)(3,4), (1,2,3) ])
    gap> irr:=IrreducibleRepresentations(G,GF(7));
    [ [ (1,2)(3,4), (1,2,3) ] -> [ [ [ Z(7)^0 ] ], [ [ Z(7)^0 ] ] ],
      
    [ (1,2)(3,4), (1,2,3) ] -> [ [ [ Z(7)^0 ] ], [ [ Z(7)^4 ] ] ],
      
    [ (1,2)(3,4), (1,2,3) ] -> [ [ [ Z(7)^0 ] ], [ [ Z(7)^2 ] ] ],
      
    [ (1,2)(3,4), (1,2,3) ] -> [
          
    [ [ 0*Z(7), Z(7)^3, Z(7)^0 ], [ 0*Z(7), Z(7)^3, 0*Z(7) ], 
    [ Z(7)^0, Z(7)^3, 0*Z(7) ] ],
          [ [ 0*Z(7), Z(7)^0, 0*Z(7) ], 
    [ 0*Z(7), 0*Z(7), Z(7)^0 ], [ Z(7)^0, 0*Z(7), 0*Z(7) ] ]
         
    ] ]
    gap> brvals := List(irr,chi-> List(ConjugacyClasses(G),c->
    BrauerCharacterValue(Image(chi, Representative(c)))));
    [ [ 1, 1, 1, 1 ], [ 1, 1, E(3)^2, E(3) ], [ 1, 1, E(3), E(3)^2 ], 
    [ 3, -1, 0, 0 ] ]
    gap> Display(brvals);
    [ [       1,       1,       1,       1 ],
      
    [       1,       1,  E(3)^2,    E(3) ],
      
    [       1,       1,    E(3),  E(3)^2 ],
      
    [       3,      -1,       0,       0 ] ]
    gap>                                               
    

    List(ConjugacyClasses(G),c->BrauerCharacterValue(Image(chi, Representative(c)))));
    #Display(brvals);
    T:=CharacterTable(G);
    Display(T);
    –>


  • polynomial
    There are various ways to construct a polynomial in GAP.

    gap> Pts:=Z(7)^0*[1,2,3];
    [ Z(7)^0, Z(7)^2, Z(7) ]
    gap> Vals:=Z(7)^0*[1,2,6];
    [ Z(7)^0, Z(7)^2, Z(7)^3 ]
    gap> g:=InterpolatedPolynomial(GF(7),Pts,Vals);
    Z(7)^5*x_1^2+Z(7)
    

    Or:

    gap> p:=3;; F:=GF(p);;
    gap> R:=PolynomialRing(F,["x1","x2"]);
    PolynomialRing(..., [ x1, x2 ])
    gap> vars:=IndeterminatesOfPolynomialRing(R);;
    gap> x1:=vars[1]; x2:=vars[2];
    x1
    x2
    gap> p:=x1^5-x2^5;
    x1^5-x2^5
    gap> DivisorsMultivariatePolynomial(p,R);
    [ x1^4+x1^3*x2+x1^2*x2^2+x1*x2^3+x2^4, x1-x2 ]
    

    Or:

    gap> x:=X(Rationals);
    x_1
    gap> f:=x+x^2+1;
    x_1^2+x_1+1
    gap> Value(f,[x],[1]);
    3
    


  • factor
    To factor a polynomial in GAP, there is one command for
    univariate polynomials (“Factors”) and another command for
    multivariate polynomials (“DivisorsMultivariatePolynomial”).For a factoring a univariate polynomial,
    GAP provides only methods over finite fields
    and over subfields of cyclotomic fields.
    Please see the
    examples given in section

    64.10 “Polynomial Factorization”
    for more details.For multivariate polynomials,
    a very slow algorithm has been implemented in GAP
    and an interface to a very fast algorithm in
    Singular
    has been implemented for those who have both Singular and
    the GAP Singular package
    installed. The former of these was
    illustrated above in
    “polynomial” above.
    (Again, the ground field must be a finite field
    or a subfields of cyclotomic fields.)
    For the latter, please see the example
    in the (GAP-)Singular manual
    FactorsUsingSingularNC.


  • roots
    There are some situtations where GAP does find the roots
    of a polynomial but GAP does not do this generally.
    (The roots must generate either a finite field
    or a subfield of a cyclotomic field.) However, there is a package called

    RadiRoot
    which must be installed which does help to do this
    for polynomials with rational coefficients
    (radiroot itself requires other packages to be installed;
    please see the webpage for more details).The “Factors” command actually has an option which allows you to
    increase the groundfield so that a factorization actually
    returns the roots. Please see the
    examples given in section

    64.10 “Polynomial Factorization”
    for more details.Here is a second appoach.

    gap> p:=3; n:=4; F:=GF(p^n); c:=Random(F); r:=2;
    3
    4
    GF(3^4)
    Z(3^4)^79
    2
    gap>  x:=X(F,1); f:=x^r-c*x+c-1;
    x_1
    x_1^2+Z(3^4)^39*x_1+Z(3^4)^36
    gap>  F_f:=FieldExtension( F, f );
    AsField( GF(3^4), GF(3^8) )
    gap>  alpha:=RootOfDefiningPolynomial(F_f);
    Z(3^4)^36
    gap> Value(f,[x],[alpha]);
    0*Z(3)
    
    

    Here is a third. First, enter the following program:

    RootOfPolynomial:=function(f,R)
     local F0,Ff,a;
     F0:=CoefficientsRing(R);
     Ff:=FieldExtension(F0,f);
     a:=RootOfDefiningPolynomial(Ff);
     return a;
    end;
    

    Here’s how this can be used to find a root:

    gap> F:=Rationals;
    Rationals
    gap> x:=X(F,1); f:=x^2+x+1;
    x_1
    x_1^2+x_1+1
    gap> R:=PolynomialRing( F, [ x ]);
    PolynomialRing(..., [ x_1 ])
    gap> a:=RootOfPolynomial(f,R);
    E(3)
    gap> # check:
    gap> Value(f,[x],[a]);
    0
    

    Related links:

    1. In the GAP Forum:

      Hensel lifting discussion
      .
    2. In the manual,

      Galois groups
      .

  • evaluate:
    The relevant command is “Value”. There are several examples already on
    this page. For others, please see the examples given in section
    64.7 Multivariate polynomials of the manual.
    For sparse uivariate polynomials, there is also the command
    “ValuePol” in section
    23.6 of the manual.


  • integer power
    This is easy and intuitive:

    gap> a:=1000; n:=100000; m:=123;
    1000
    100000
    123
    gap> a^n mod m;
    1
    
    


  • matrix power:
    This too is easy and intuitive:

    gap> A:=[[1,2],[3,4]]; n:=100000; m:=123;
    [ [ 1, 2 ], [ 3, 4 ] ]
    100000
    123
    gap> A^n mod m;
    [ [ 1, 41 ], [ 0, 1 ] ]
    

  • polynomial power
    GAP allows you to do arithmetic over the polynomial
    ring R[x], where R = Z/nZ (where n is a positive integer).
    Here’s an example.

    gap> Z4:=ZmodnZ(4);
    (Integers mod 4)
    gap> R:=UnivariatePolynomialRing(Z4,1);
    PolynomialRing(..., [ x ])
    gap> x:=IndeterminatesOfPolynomialRing(R)[1];
    x
    gap> I:=TwoSidedIdealByGenerators( R,[x^8-x^0]);
    two-sided ideal in PolynomialRing(..., [ x ]), (1 generators)
    gap> gen:=x^8-x^0;
    x8-ZmodnZObj(1,4)
    gap> QuotientRemainder(R,x^8,gen);
    [ ZmodnZObj(1,4), ZmodnZObj(1,4) ]
    gap> QuotientRemainder(R,x^15,gen);
    [ x^7, x^7 ]
    gap> QuotientRemainder(R,x^15+x^8,gen);
    [ x^7+ZmodnZObj(1,4), x^7+ZmodnZObj(1,4) ]
    gap> PowerMod( R, x+x^0, 15, gen );
    ZmodnZObj(0,4)
    gap> PowerMod( R, x, 15, gen );
    x^7
    
    


  • Groebner basis
    GAP’s Groebner bases algorithms are relatively slow
    and are included mostly for simple examples and for
    teaching purposes. However, a GAP interface to a very
    fast algorithm in Singular
    has been implemented for those who have both Singular and
    the
    GAP Singular package
    installed. The former of these is
    illustrated in section
    64.17 Groebner bases of the GAP manual.
    For the latter, please see the example
    in the (GAP-)Singular manual
    GroebnerBasis.


  • normal subgroup:
    Here is an example:

    gap> G := AlternatingGroup( 5 );
    Group( (1,2,5), (2,3,5), (3,4,5) )
    gap> normal := NormalSubgroups( G );
    [ Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ), [  ] ), 
      Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ), 
        [ (1,2)(3,4), (1,3)(4,5), (1,4)(2,3) ] ) ]
    

    Related links:

    1. Please see Volkmar Felsch’s
      GAP Forum response to a related question.
    2. The

      xgap
      package displays subgroup lattices graphically.

  • abelian subgroup
    One idea to compute all the abelian subgroups is to compute all the
    subgroups then “filter” out the abelian ones.
    Here is an illustration, taked from a
    GAP Forum response Volkmar Felsch.

    gap> G := AlternatingGroup( 5 );
    Group( (1,2,5), (2,3,5), (3,4,5) )
    gap> classes := ConjugacyClassesSubgroups( G );
    [ ConjugacyClassSubgroups( Group( (1,2,5), (2,3,5), 
        (3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ), [  ] ) ),
      ConjugacyClassSubgroups( Group( (1,2,5), (2,3,5), 
        (3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ), 
        [ (2,3)(4,5) ] ) ), ConjugacyClassSubgroups( Group( (1,2,5), 
        (2,3,5), (3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ), 
        [ (3,4,5) ] ) ), ConjugacyClassSubgroups( Group( (1,2,5), 
        (2,3,5), (3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ), 
        [ (2,3)(4,5), (2,4)(3,5) ] ) ), ConjugacyClassSubgroups( Group( 
        (1,2,5), (2,3,5), (3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), 
        (3,4,5) ), [ (1,2,3,4,5) ] ) ), ConjugacyClassSubgroups( Group( 
        (1,2,5), (2,3,5), (3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), 
        (3,4,5) ), [ (3,4,5), (1,2)(4,5) ] ) ), 
      ConjugacyClassSubgroups( Group( (1,2,5), (2,3,5), 
        (3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ), 
        [ (1,2,3,4,5), (2,5)(3,4) ] ) ), ConjugacyClassSubgroups( Group( 
        (1,2,5), (2,3,5), (3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), 
        (3,4,5) ), [ (2,3)(4,5), (2,4)(3,5), (3,4,5) ] ) ), 
      ConjugacyClassSubgroups( Group( (1,2,5), (2,3,5), (3,4,5) ), Group( 
        (1,2,5), (2,3,5), (3,4,5) ) ) ]
    gap> cl := classes[4];
    ConjugacyClassSubgroups( Group( (1,2,5), (2,3,5), 
    (3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ), 
    [ (2,3)(4,5), (2,4)(3,5) ] ) )
    gap> length := Size( cl );
    5
    gap> rep := Representative( cl );
    Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ), 
    [ (2,3)(4,5), (2,4)(3,5) ] )
    gap> order := Size( rep );
    4
    gap> IsAbelian( rep );
    true
    gap> abel := Filtered( classes, cl -> IsAbelian( Representative( cl ) ) );
    [ ConjugacyClassSubgroups( Group( (1,2,5), (2,3,5), 
        (3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ), [  ] ) ),
      ConjugacyClassSubgroups( Group( (1,2,5), (2,3,5), 
        (3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ), 
        [ (2,3)(4,5) ] ) ), ConjugacyClassSubgroups( Group( (1,2,5), 
        (2,3,5), (3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ), 
        [ (3,4,5) ] ) ), ConjugacyClassSubgroups( Group( (1,2,5), 
        (2,3,5), (3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ), 
        [ (2,3)(4,5), (2,4)(3,5) ] ) ), ConjugacyClassSubgroups( Group( 
        (1,2,5), (2,3,5), (3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), 
        (3,4,5) ), [ (1,2,3,4,5) ] ) ) ]
    

  • homology
    This depends on how the group is given. For example, suppose that
    G is a permutation group with generators genG and
    H is a permutation group with generators genH. To find a
    homomorphism from G to H, one may use the
    “GroupHomomorphismByImages” or “GroupHomomorphismByImagesNC”
    commands. For examples of the syntax, please see
    section
    38.1 Creating Group Homomorphisms.Here’s an illustration of how to convert a finitely presented
    group into a permutation group.

    gap> p:=7;
    7
    gap> G:=PSL(2,p);
    Group([ (3,7,5)(4,8,6), (1,2,6)(3,4,8) ])
    gap> H:=SchurCover(G);
    fp group of size 336 on the generators [ f1, f2, f3 ]
    gap> iso:=IsomorphismPermGroup(H);
    [ f1, f2, f3 ] -> [ (1,2,4,3)(5,9,7,10)(6,11,8,12)(13,14,15,16),
      (2,5,6)(3,7,8)(11,13,14)(12,15,16), (1,4)(2,3)(5,7)(6,8)(9,10)(11,12)(13,
        15)(14,16) ]
    gap> H0:=Image(iso);                       # 2-cover of PSL2
    Group([ (1,2,4,3)(5,9,7,10)(6,11,8,12)(13,14,15,16),
      (2,5,6)(3,7,8)(11,13,14)(12,15,16), (1,4)(2,3)(5,7)(6,8)(9,10)(11,12)(13,
        15)(14,16) ])
    gap> IdGroup(H0);
    [ 336, 114 ]
    gap> IdGroup(SL(2,7));
    [ 336, 114 ]
    gap>                
    

  • semi-direct product(Contributed by Nilo de Roock):
    As you can easily verify, D8 is isomorphic to C2:C4. Or in GAP…

    N:=CyclicGroup(IsPermGroup,4);
    G:=CyclicGroup(IsPermGroup,2);
    AutN:=AutomorphismGroup(N);
    f:=GroupHomomorphismByImages(G,AutN,GeneratorsOfGroup(G),[Elements(AutN)[2]]);
    NG:=SemidirectProduct(G,f,N);
    

    Verify with

    StructureDescription(NG);
    

  • semi-direct products(Contributed by Nilo de Roock):
    The following shows how to construct all non-abelian groups
    of order 12 as semi-direct products. These products are not
    trivial yet small enough to verify by hand.

    #D12 = (C2 x C2) : C3
    G1:=CyclicGroup(IsPermGroup,2);
    G2:=CyclicGroup(IsPermGroup,2);
    G:=DirectProduct(G1,G2);
    N:=CyclicGroup(IsPermGroup,3);
    AutN:=AutomorphismGroup(N);
    f:=GroupHomomorphismByImages(G,AutN,[Elements(G)[1],Elements(G)[2],Elements(G)[3],Elements(G)[4]],[Elements(AutN)[1],Elements(AutN)[2],Elements(AutN)[1],Elements(AutN)[2]]);
    NG:=SemidirectProduct(G,f,N);
    Print(str(NG));
    Print("\n");
    
    #T = C4 : C3
    G:=CyclicGroup(IsPermGroup,4);
    N:=CyclicGroup(IsPermGroup,3);
    AutN:=AutomorphismGroup(N);
    f:=GroupHomomorphismByImages(G,AutN,[Elements(G)[1],Elements(G)[2],Elements(G)[3],Elements(G)[4]],[Elements(AutN)[1],Elements(AutN)[2],Elements(AutN)[1],Elements(AutN)[2]]);
    NG:=SemidirectProduct(G,f,N);
    Print(str(NG));
    Print("\n");
    
    #A4 = C3 : (C2 x C2)
    G:=CyclicGroup(IsPermGroup,3);
    N1:=CyclicGroup(IsPermGroup,2);
    N2:=CyclicGroup(IsPermGroup,2);
    N:=DirectProduct(G1,G2);
    AutN:=AutomorphismGroup(N);
    f:=GroupHomomorphismByImages(G,AutN,[Elements(G)[1],Elements(G)[2],Elements(G)[3]],[Elements(AutN)[1],Elements(AutN)[4],Elements(AutN)[5]]);
    NG:=SemidirectProduct(G,f,N);
    Print(str(NG));
    Print("\n");
    

  • cohomology
    GAP will compute the Schur multiplier
    H2(G,C) using the
    “AbelianInvariantsMultiplier” command.
    Here is an example showing how to find H2(A5,C),
    where A5 is the alternating group on 5 letters.

    gap> A5:=AlternatingGroup(5);
    Alt( [ 1 .. 5 ] )
    gap> AbelianInvariantsMultiplier(A5);
    [ 2 ]
    

    So, H2(A5,C) is Z/2Z.

    Related links:

    1. See section

      37.23
      and
      section

      37.24
      of the GAP manual.
    2. See D. Holt’s GAP package
      cohomolo.

“Circle decoding” of the [7,4,3] Hamming code

This is a well-known trick but I’m posting it here since I often have a hard time tracking it down when I need it for an introductory coding theory talk or something. Hopefully someone else will find it amusing too!

Let F = GF(2) and let C be the set of all vectors in the third column below (for simplicity, we omit commas and parentheses, so 0000000 is written instead of (0,0,0,0,0,0,0), for example).

The [7,4,3] Hamming code
  decimal     binary     Hamming [7,4] 
0 0000 0000000
1 0001 0001110
2 0010 0010101
3 0011 0011011
4 0100 0100011
5 0101 0101101
6 0110 0110110
7 0111 0111000
8 1000 1000111
9 1001 1001001
10 1010 1010010
11 1011 1011100
12 1100 1100100
13 1101 1101010
14 1110 1110001
15 1111 1111111

This is a linear code of length 7, dimension 4, and minimum distance 3. It is called the Hamming [7,4,3]-code.
In fact, there is a mapping from F^4 to C given by \phi(x_1,x_2,x_3,x_4)={\bf y}, where
{\bf y}= \left( \begin{array}{c} y_1 \\ y_2 \\ y_3 \\ y_4 \\ y_5 \\ y_6 \\ y_7 \end{array} \right) = \left( \begin{array}{cccc} 1&0&0&0 \\ 0&1&0&0 \\ 0&0&1&0 \\ 0&0&0&1 \\ 1&0&1&1 \\ 1&1&0&1 \\ 1&1&1&0 \end{array} \right) \left( \begin{array}{c} x_1 \\ x_2 \\ x_3 \\ x_4 \end{array} \right) \ \pmod{2}. Moreover, the matrix G=\left(\begin{array}{ccccccc} 1&0&0&0&1&1&1 \\ 0&1&0&0&0&1&1 \\ 0&0&1&0&1&0&1 \\ 0&0&0&1&1&1&0 \end{array}\right) is a generator matrix.

Now, suppose a codeword c \in C is sent over a noisy channel and denote the received word by {\bf w}=(w_1,w_2,w_3,w_4,w_5,w_6,w_7). We assume at most 1 error was made.

  1. Put w_i in the region of the Venn diagram above associated to coordinate i in the table below, i=1,2,...,7.
  2. Do parity checks on each of the circles A, B, and C.

Decoding table
  parity failure region(s)     error position  
none none
A, B, and C 1
B and C 2
A and C 3
A and B 4
A 5
B 6
C 7

Exercise: Decode {\bf w} = (0,1,0,0,0,0,1) in the binary Hamming code using this algorithm.
(This is solved at the bottom of this column.)

In his 1976 autobiography Adventures of a Mathematician, Stanislaw Ulam [U] poses the following problem:

Someone thinks of a number between one and one million (which is just less than 220). Another person is allowed to ask up to twenty questions, to which the first person is supposed to answer only yes or no. Obviously, the number can be guessed by asking first: Is the number in the first half-million? and then again reduce the reservoir of numbers in the next question by one-half, and so on. Finally, the number is obtained in less than log2(1000000). Now suppose one were allowed to lie once or twice, then how many questions would one need to get the right answer?

We define Ulam’s Problem as follows: Fix integers M\geq 1 and e\geq 0. Let Player 1 choose the number from the set of integers 0,1, ...,M and Player 2 ask the yes/no questions to deduce the number, to which Player 1 is allowed to lie at most e times. Player 2 must discern which number Player 1 picked with a minimum number of questions with no feedback (in other words, all the questions must be provided at once)

As far as I know, the solution to this version of Ulam’s problem without feedback is still unsolved if e=2. In the case e=1, see [N] and [M]. (Also, [H] is a good survey.)

Player 1 has to convert his number to binary and encode it as a Hamming [7,4,3] codeword. A table containing all 16 codewords is included above for reference. Player 2 then asks seven questions of the form, “Is the i-th bit of your 7-tuple a 1?” Player 1’s answers form the new 7-tuple, (c_1,c_2,...,c_7), and each coordinate is placed in the corresponding region of the circle. If Player 1 was completely truthful, then the codeword’s parity conditions hold. This means that the 7-tuple generated by Player 2’s questions will match a 7-tuple from the codeword table above. At this point, Player 2 just has to decode his 7-tuple into an integer using the codeword table above to win the game. A single lie, however, will yield a 7-tuple unlike any in the codeword table. If this is the case, Player 2 must error-check the received codeword using the three parity check bits and the decoding table above. In other words, once Player 2 determines the position of the erroneous bit, he corrects it by “flipping its bit”. Decoding the corrected codeword will yield Player 1’s original number.

References

[H] R. Hill, “Searching with lies,” in Surveys in Combinatorics, ed. by P. Rowlinson, London Math Soc, Lecture Notes Series # 218.

[M] J. Montague, “A Solution to Ulam’s Problem with Error-correcting Codes”

[N] I. Niven, “Coding theory applied to a problem of Ulam,” Math Mag 61(1988)275-281.

[U] S. Ulam, Adventures of a mathematician, Scribner and Sons, New York, 1976 .


Solution to exercise using SAGE:


sage: MS = MatrixSpace(GF(2), 4, 7)
sage: G = MS([[1,0,0,0,1,1,1],[0,1,0,0,0,1,1],[0,0,1,0,1,0,1],[0,0,0,1,1,1,0]])
sage: C = LinearCode(G)
sage: V = VectorSpace(GF(2), 7)
sage: w = V([0,1,0,0,0,0,1])
sage: C.decode(w)
(0, 1, 0, 0, 0, 1, 1)

In other words, Player picked 4 and lied on the 6th question.

Here is a Sage subtlety:

sage: C = HammingCode(3, GF(2))
sage: C
Linear code of length 7, dimension 4 over Finite Field of size 2
sage: V = VectorSpace(GF(2), 7)
sage: w = V([0,1,0,0,0,0,1])
sage: C.decode(w)
(1, 1, 0, 0, 0, 0, 1)

Why is this decoded word different? Because the Sage Hamming code is distinct (though “equivalent” to) the Hamming code we used in the example above.

Unfortunately, SAGE does not yet do code isomorphisms (at least not as easily as GUAVA), so we use GUAVA’s CodeIsomorphism function, which calls J. Leon’s GPL’s desauto C code function:


gap> C1 := GeneratorMatCode([[1,0,0,1,0,1,0],[0,1,0,1,0,1,1],[0,0,1,1,0,0,1],[0,0,0,0,1,1,1]],GF(2));
a linear [7,4,1..3]1 code defined by generator matrix over GF(2)
gap> C2 := GeneratorMatCode([[1,0,0,0,1,1,1],[0,1,0,0,0,1,1],[0,0,1,0,1,0,1],[0,0,0,1,1,1,0]],GF(2));
a linear [7,4,1..3]1 code defined by generator matrix over GF(2)
gap> CodeIsomorphism(C1,C2);
(2,6,7,3)
gap> Display(GeneratorMat(C1));
1 . . 1 . 1 .
. 1 . 1 . 1 1
. . 1 1 . . 1
. . . . 1 1 1
gap> Display(GeneratorMat(C2));
1 . . . 1 1 1
. 1 . . . 1 1
. . 1 . 1 . 1
. . . 1 1 1 .

Now we see that the permutation (2,6,7,3) sends the “SAGE Hamming code” to the “circle Hamming code”:


sage: H = HammingCode(3, GF(2))
sage: G = MS([[1,0,0,0,1,1,1],[0,1,0,0,0,1,1],[0,0,1,0,1,0,1],[0,0,0,1,1,1,0]])
sage: C = LinearCode(G)
sage: C.gen_mat()
[1 0 0 0 1 1 1]
[0 1 0 0 0 1 1]
[0 0 1 0 1 0 1]
[0 0 0 1 1 1 0]
sage: S7 = SymmetricGroup(7)
sage: g = S7([(2,6,7,3)])
sage: H.permuted_code(g) == C
True