# How do I construct … in GAP?

“How do I construct … in GAP?” You may view the html source code
for the GAP commands without the output or GAP prompt.

David Joyner.

Questions

 How do I construct a … group? permutation dihedral  cyclicconjugacy classes of a finitely presented How do I … a polynomial? factor find roots of evaluate Groebner basis of ideal of Brauer characters 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 … ?

• 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:
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.
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

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


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
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) ] ) ]


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.

1. See section

37.23
and
section

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

# Real world applications of representation theory

### (Subtitle: Representation theorists will rule the world one day just you wait)

This post describes some applications of representation theory of non-abelian groups to various fields and gives some references.

• Engineering.
• Tensegrity – the design of “strut-and-cable” constructions.Want to build a building with cables and struts but don’t know representation theory? Check out these references:
• R. Connelly and A. Back, “Mathematics and tensegrity”, Amer Scientist, April-May 1998, pages 142-151
• symmetric tensegrities
• Telephone network designs.This is the information age with more and more telephone lines needed every day. Want to reach out and touch someone? You need representation theory.
• F. Bien, “Construction of telephone networks by group representations”, Notices A. M. S. 36(1989)5-22
• Nonlinear network problems.This is cheating a little since the works in the reference below really use the theory of Lie groups instead of representation theory itself. Still, there is a tangential relation at least between representation theory of Lie groups and the solution to certain nonlinear network problems.
• C. Desoer, R. Brockett, J. Wood, R. Hirshorn,
A. Willsky, G. Blankenship, Applications of Lie group theory to nonlinear network problems, (Supplement to IEEE Symposium on Circuit Theory, 1974), Western Periodicals Co., N. Hollywood, CA, 1974
• Control theory.
• R. W. Brockett, “Lie theory and control systems defined on spheres”, SIAM J on Applied Math 25(1973) 213-225
• Robotics.The future is not in plastics (see the movie “The Graduate“) but in robotics.
How do you figure out their movements before building them? You guessed it, using representation theory.

• G. Chirikjian, “Determination and synthesis of discretely actuated manipulator workspaces using harmonic analysis”, in Advances in Robotic Kinematics, 5, 1996, Springer-Verlag
• G. Chirikjian and I. Ebert-Uphoff, “Discretely actuated manipulator workspace generation by closed-form convolution”, in ASME Design Engineering Technical Conference, August 18-22 1996
• Radar design.W. Schempp, Harmonic analysis on the Heisenberg nilpotent Lie group, with
applications to signal theory
, Longman Scientific & Technical, New York (Copublished in the U.S. with Wiley), 1986.
• Antenna design.B. Hassibi, B. Hochwald, A. Shokrollahi, W. Sweldens, “Representation theory for high-rate multiple antenna code design,” 2000 preprint (see A. Shokrollahi’s site for similar works).
• Design of stereo systems.We’re talkin’ quadrophonic state-of-the-art.
• K. Hannabus, “Sound and symmetry”, Math. Intelligencer, 19, Fall 1997, pages 16-20
• Coding theory. Interesting progress in coding theory has been made using group theory and representation theory. Here are a few selected references.
• F. MacWilliams and N. Sloane, The Theory of Error-Correcting Codes,
North-Holland/Elsevier, 1993 (8th printing)
• I. Blake and R. Mullin, Mathematical Theory of Coding, Academic Press, 1975
49(1995)215-223
• J.-P. Tillich and G. Zemor,
“Optimal cycle codes constructed from Ramanujan graphs,” SIAM J on Disc. Math. 10(1997)447-459
• H. Ward and J. Wood, “Characters and the equivalence of codes,” J. Combin. Theory A 73348-352
• J. Lafferty and D. Rockmore, “Spectral Techniques for Expander Codes” , (Extended Abstract) 1997 Symposium on Theory of Computation (available
at  Dan Rockmore’s web page)
• Mathematical physics.
Any complete list of books and papers in this field which use representation theory would be much too long for the limited goal we have here (which is simply
to list some real-world applications). A small selection is given below.

• Differential equations (such as the heat equation, Schrodinger wave equation, etc).M. Craddock, “The symmetry groups of linear partial differential equations
and representation theory, I” J. Diff. Equations 116(1995)202-247
• Mechanics.
• D.H. Sattinger, O.L. Weaver, Lie Groups and Algebras With Applications to Physics, Geometry, and Mechanics (Applied Mathematical Sciences, Vol 61) , Springer Verlag, 1986
• Johan Belinfante, “Lie algebras and inhomogeneous simple materials”,
SIAM J on Applied Math 25(1973)260-268
• Models for elementary particles.
• Quantum mechanics.
• Eugene Wigner, “Reduction of direct products and restriction of representations to subgroups: the everyday tasks of the quantum theorists”, SIAM J on Applied Math 25(1973) 169-185
• V. Vladimirov, I. Volovich, and E. Zelenov, “Spectral theory in p-adic quantum mechanics and representation theory,” Soviet Math. Doklady 41(1990)40-44
• Y. Manin, “Reflections on arithmetical physics,” in Conformal invariance and string theory, Academic Press, 1989, pages 293-303
• V. Vladimirov, I. Volovich, and E. Zelenov, p-adic analysis and mathematical physics, World Scientific, 1994
• V. Vladimirov, “On the Freund-Witten adelic formula for Veneziano amplitudes,” Letters in Math. Physics 27(1993)123-131
• Mathematical chemistry.
• Spectroscopy.B. Judd, “Lie groups in Atomic and molecular spectroscopy”, SIAM J on Applied Math 25(1973) 186-192
• Crystallography.
• G. Ramachandran and R. Srinivasan, Fourier methods in crystallography,
New York, Wiley-Interscience, 1970.
• T. Janssen, Crystallographic groups, North-Holland Pub., London, 1973.
• J. Zak, A. Casher, M. Gluck, Y. Gur, The irreducible representations of space groups, W. A. Benjamin, Inc., New York, 1969.
• Molecular strucure of the Buckyball.
• F. Chung and S. Sternberg, “Mathematics and the buckyball”, American Scientist 83(1993)56-71
• F. Chung, B. Kostant, and S. Sternberg, “Groups and the buckyball”, in Lie theory and geometry, (ed. J.-L. Brylinski et al), Birkhauser, 1994
• G. James, “The representation theory for the Buckminsterfullerene,” J. Alg. 167(1994)803-820
• Knot theory (which, in turn, has applications to modeling DNA) uses representation theory. F. Constantinescu and F. Toppan, “On the linearized Artin braid representation,” J. Knot Theory and its Ramifications, 2(1993)
• The Riemann hypothesis.
Think you’re going to solve the Riemann hypothesis without using
representation theory? Check this paper out: A. Connes, “Formule de traces en geometrie non-commutative et hypothese de Riemann”, C. R. Acad. Sci. Paris 323 (1996)1231-1236. (For those who argue that this is not a real-world application, we refer to Barry Cipra’s article, “Prime Formula Weds Number Theory and Quantum Physics,” Science, 1996 December 20, 274, no. 5295, page 2014, in Research News.)
• Circuit design, statistics, signal processing, …
See the survey paper
D. Rockmore, “Some applications of generalized FFTs” in Proceedings of the DIMACS
Workshop on Groups and Computation, June 7-10, 1995 eds. L. Finkelstein and W. Kantor, (1997) 329–369. (available at  Dan Rockmore’s web page)
• Vision – See the survey papers by Jacek Turski:Geometric Fourier Analysis of the Conformal Camera for Active Vision, SIAM Review, Volume 46 Issue 2 pages 230-255, 2004 Society for Industrial and Applied Mathematics, and, Geometric Fourier Analysis for Computational Vision, JFAA 11, 1-23, 2005.

# Complements in the symmetric group

About 20 years ago I was asked a question of Herbert Kociemba, a computer scientist who has one of the best Rubik’s cube solving programs known. Efficient methods of storing permutations in $S_E$ and $S_V$ (the groups of all permutations of the edges $E$ and vertices $V$, respectively, of the Rubik’s cube) are needed, hence leading naturally to the concept of the complement of $S_m$ in $S_n$. Specifically, he asked if $S_8$ has a complement in $S_{12}$ (this terminology is defined below). The answer is,
as we shall see, ”no.” Nonetheless, it turns out to be possible to introduce a slightly more general notion of a “$k$-tuple of complementary subgroups” (defined below) for which the answer to the analogous question is ”yes.”

This post is a very short summary of a paper I wrote (still unpublished) which can be downloaded here.

# Splitting fields of representations of generalized symmetric groups, 8

In this post, we give an example.

Let $G=C_3^8\, >\!\!\lhd \, S_8$ and let

$\pi = \theta_{\mu,\rho}=Ind_{G_\mu}^G(\mu\cdot \tilde{\rho}),$

where $\mu$ is a character of $C_3^8$ and $\rho$ is an irreducible representation of its stabilizer in $S_8$, $(S_8)_\mu$.

The real representations $\pi$ of $G$ are the ones for which

1. $\mu$ is represented by a character of the form

$(1,1,1,1,1,1,\omega,\omega^2) \ {\rm or}\ (1,1,...,1),$

and $\rho$ anything, or

2. $\mu$ is represented by a character of the form

$(1,1,1,1,\omega,\omega,\omega^2,\omega^2), \rho_1=(\pi_1,\pi_2,\pi_2)\in (S_4)^*\times (S_2)^*\times (S_2)^*,$

or

3. $\mu$ is represented by a character of the form

$(\omega,\omega,\omega,\omega,\omega^2,\omega^2,\omega^2,\omega^2), \rho_1=(\pi_2,\pi_2)\in (S_4)^*\times (S_4)^*,$

or

4. $\mu$ is represented by a character of the form

$(1,1,\omega,\omega,\omega,\omega^2,\omega^2,\omega^2), \rho_1=(\pi_1,\pi_2,\pi_2)\in (S_2)^*\times (S_3)^*\times (S_3)^*.$

The complex representations of $G$ are: the representations
whose characters have at least one complex value. Such representations $\pi = \theta_{\mu,\rho}$ are characterized by the fact that $(\mu,\rho)$ is inequivalent to $(\overline{\mu},\rho)$ under the obvious $S_8$-equivalence relation (which can be determined from the equivalence relation for representations in $G^*$).

The complex representations of $G$ are the remaining representations not included in the above list.

There are no quaternionic representations of $G$.

The claims above follow from the fact that a representation
$\theta_{\rho,\mu}$ is complex if and only if $\mu$ is not self-dual.

# Splitting fields of representations of generalized symmetric groups, 7

In this post, we discover which representations of the generalized symmetric group $G = S_n\ wr\ C_\ell = C_\ell^n\, >\!\!\lhd \, S_n$ can be realized over a given abelian extension of ${\mathbb{Q}}$.

Let $\theta_{\mu,\rho}\in G^*$ be the representation defined previously, where $\rho\in ((S_n)_\mu)^*$.

Let $K\subset {\mathbb{Q}}(\zeta_\ell)$ be a subfield, where $\zeta_\ell$ is a primitive $\ell^{th}$ root of unity. Assume $K$ contains the field generated by the values of the character of $\theta_{\mu,\rho}$. Assume $K/{\mathbb{Q}}$ is Galois and let $\Gamma_K=Gal({\mathbb{Q}}(\zeta_\ell)/K)$. Note if we regard $C_\ell$ as a subset of ${\mathbb{Q}}(\zeta_\ell)$ then there is an induced action of $\Gamma_K$ on $C_\ell$,

$\sigma:\mu \longmapsto \mu^\sigma, \ \ \ \ \ \ \ \ \ \mu\in (C_\ell)^*,\ \ \sigma\in \Gamma_K,$

where $\mu^\sigma(z)=\mu(\sigma^{-1}(z))$, $z\in C_\ell$. This action extends to an action on $(C_\ell^n)^*=(C_\ell^*)^n$.

Key Lemma:
In the notation above, $\theta_{\mu,\rho}\cong\theta_{\mu,\rho}^\sigma$ if and only if $\mu$ is equivalent to $\mu^\sigma$ under the action of $S_n$ on $(C_\ell^n)^*$.

Let

$n_\mu(\chi)=|\{i\ |\ 1\leq i\leq n,\ \mu_i=\chi\}|,$

where $\mu=(\mu_1,...,\mu_n)\in (C_\ell^n)^*$ and $\chi\in C_\ell^*$.

Theorem: The character of $\theta_{\mu,\rho}\in G^*$ has values in $K$ if and only if $n_\mu(\chi)=n_\mu(\chi^\sigma)$,
for all $\sigma\in \Gamma_K$ and all $\chi\in C_\ell^*$.

This theorem is proven in this paper.

We now determine the splitting field of any irreducible character of a generalized symmetric group.

Theorem: Let $\chi=tr(\theta_{\rho,\mu})$ be an irreducible character of $G=S_n\ wr\ C_\ell$. We have

$Gal({\mathbb{Q}}(\zeta_\ell)/{\mathbb{Q}}(\chi))= Stab_\Gamma(\chi).$

This theorem is also proven in this paper.

In the next post we shall give an example.

# Splitting fields of representations of generalized symmetric groups, 6

This post shall list some properties of the Schur index $m_F(G)$ in the case where $G = S_n\ wr\ C_\ell$ is a generalized symmetric group and $F$ is either the reals or rationals.

Let $\eta_k(z)=z^k$, for $z\in C_\ell$, $1\leq k\leq \ell$.

Theorem: Let $G = S_n\ wr\ C_\ell$. Let $\mu=(\eta_{e_1},...,\eta_{e_n})\in (C_\ell^n)^*$, for some $e_j\in \{0,...,\ell-1\}$, and let $\rho\in (S_n)_\mu^*$. Let
$\chi$ denotes the character of $\theta_{\mu,\rho}$.

1. Suppose that one of the following conditions holds:
1. $4|\ell$ and $\overline{e_1+...+e_n}$ divides $\overline{\ell/4}$ in ${\mathbb{Z}}/\ell {\mathbb{Z}}$, or
2. $(e_1+...+e_n,\ell)=1$,

Then $m_{\Bbb{Q}}(\chi)=1$.

2. Suppose that one of the following conditions holds:
1. $(n,\ell)=1$, $4|\ell$, and $(e_1+...+e_n)x\equiv \ell /4\ ({\rm mod}\ \ell)$ is not solvable, or
2. $(n,\ell)=1$ and $(e_1+...+e_n,\ell)>1$.

Then $m_{\mathbb{Q}}(\chi\eta_1)=1$.

This theorem is proven in this paper. Benard has shown that $m_{\mathbb{Q}}(\chi)=1$, for all $\chi$ as in the above theorem.

Since the Schur index over ${\mathbb{Q}}$ of any irreducible character $\chi$ of a generalized symmetric group $G$ is equal to $1$, each such character is associated to a representation $\pi$ all of whose matrix coefficients belong to the splitting field ${\mathbb{Q}}(\chi)$.

What is the splitting field ${\mathbb{Q}}(\chi)$, for $\chi\in G^*$?

This will be addressed in the next post.

# Splitting fields of representations of generalized symmetric groups, 5

It is a result of Benard (Schur indices and splitting fields of the unitary reflection groups, J. Algebra, 1976) that the Schur index over ${\mathbb{Q}}$ of any irreducible character of a generalized symmetric group is equal to $1$. This post recalls, for the sake of comparison with the literature, other results known about the Schur index in this case.

Suppose that $G$ is a finite group and $\pi \in G^*$ is an irreducible representation of $G$, $\pi :G\rightarrow Aut(V)$, for some complex vector space $V$. We say that $\pi$ may be realized over a subfield $F\subset {\mathbb{C}}$ if there is an $F$-vector space $V_0$ and an action of $G$ on $V_0$ such that $V$ and ${\mathbb{C}}\otimes V_0$ are equivalent representations of $G$, where $G$ acts on ${\mathbb{C}}\otimes V_0$ by “extending scalars” in $V_0$ from $F$ to ${\mathbb{C}}$. Such a representation is called an $F$-representation. In other words, $\pi$ is an $F$-representation provided it is equivalent to a representation which can be written down explicitly using matrices with entries in $F$.

Suppose that the character $\chi$ of $\pi$ has the property that

$\chi(g)\in F, \ \ \ \ \ \ \forall g\in G,$

for some subfield $F\subset {\mathbb{C}}$ independent of $g$. It is unfortunately true that, in general, $\pi$ is not necessarily an $F$-representation. However, what is remarkable is that, for some $m\geq 1$, there are $m$ representations, $\pi_1,...,\pi_m$, all equivalent to $\pi$, such that $\pi_1\oplus ...\oplus \pi_m$ is an $F$-representation. The precise theorem is the following remarkable fact.

Theorem: (Schur) Let $\chi$ be an irreducible character and let $F$ be any field containing the values of $\chi$. There is an integer $m \geq 1$ such that $m\chi$ is the character of an $F$-representation.

The smallest $m\geq 1$ in the above theorem is called the Schur index and denoted $m_F(\chi)$.

Next, we introduce some notation:

1. let ${\mathbb{R}}(\pi) = {\mathbb{R}}(\chi)$ denote the extension field of ${\mathbb{R}}$ obtained by adjoining all the values of $\chi(g)$\ ($g\in G$), where $\chi$ is the character of $\pi$,
2. let $\nu(\pi) = \nu(\chi)$ denote the Frobenius-Schur indicator of $\pi$ (so $\nu(\pi)= {1\over |G|}\sum_{g\in G} \chi(g^2)$),
3. let $m_{\mathbb{R}}(\pi) = m_{\mathbb{R}}(\chi)$ denote the Schur multiplier of $\pi$ (by definition, the smallest integer $m\geq 1$ such that $m\chi$ can be realized over ${\mathbb{R}}$ (this integer exists, by the above-mentioned theorem of Schur).

The following result shows how the Schur index behaves under induction (see Proposition 14.1.8 in G. Karpilovsky,
Group representations, vol. 3, 1994).

Proposition: Let $\chi$ be an irreducible character of $G$ and let $\psi$ denote an irreducible character of a subgroup $H$ of $G$. If $= 1$ then $m_{\Bbb{R}}(\chi)$ divides $m_{\Bbb{R}}(\psi)$.

A future post shall list some properties of the Schur index in the case where $G$ is a generalized symmetric group and $F$ is either the reals or rationals.