Falling into the GAP, Part 1

GAP is a computational algebra package, which is incredibly good for working with groups - as in Group Theory. Although Computer Algebra Packages are quite common, GAP seems to be unique in its specialization of Computational Group Theory. The only similar package I am aware of is Magma (which is proprietary and not free). GAP can run on Windows, MacOS, and Linux. Since I usually use Ubuntu Desktop (17.10), I installed GAP using

sudo apt-get install gap

First Play

To get a feel of GAP, let's go through some typical and simple commands. First, let's create a symmetric group on 8 elements (i.e. \(Sym_{8}\)). We know \(Sym_{8}\) can be generated by two permutations; one involution and one permutation of order 8.

gap> s8 := Group( (1,2), (1,2,3,4,5,6,7,8) );
Group([ (1,2), (1,2,3,4,5,6,7,8) ])

What are the conjugacy classes of \(Sym_{8}\)? First, let's quickly define what we mean by a conjugacy class. Let \(G\) be a finite group and let \(a,b \in G\). Then we say \(a\) and \(b\) are in the same conjugacy class if and only if there exists some \(c\) in \(G\) such that \(c^{-1}ac=b\). Conjugate elements form an equivalence class, and the number of conjugacy classes of \(G\) is a fundamental property of \(G\). Since conjugacy classes are equivalence classes, we can represent each class by a singular element. In Gap we can do:

gap> cc := ConjugacyClasses(s8);
[ ()^G, (1,4)(2,3)(5,7)(6,8)^G, (1,7,4,5)(2,6,3,8)^G, (1,4)(6,8)^G, 
  (1,6,4,8)(5,7)^G, (1,6,4,8)(2,3)(5,7)^G, (1,6,5,7,3,2,4,8)^G, 
  (1,4,5)(3,6,8)^G, (1,8,4,3,5,6)(2,7)^G, (2,7)^G, (1,4,5)(2,7)(3,6,8)^G, 
  (3,6,8)^G, (2,7)(3,8,6)^G, (1,4)(2,3)(6,8)^G, (1,6,4,8)^G, 
  (1,4)(2,5,3)(6,8)^G, (1,8,4,6)(2,3,5)^G, (1,2,8,3,5)^G, (1,3,2,5,8)(4,6)^G, 
  (1,8,4,3,5,6)^G, (1,8,3,4,2,5,7)^G, (1,3,2,5,8)(4,7,6)^G ]

The ConjugacyClass function gives a long list of permutations. Each permutation represents one conjugacy class. How many classes are there?

gap> Size(cc);
22

We get 22 conjugacy classes.

A closer Look

Now we have played a little with GAP, it would be good to try to understand more about it. The GAP package has been in development in some form since 1985. It seems there are many contributors to the main source code, and the project is a collaboration between several and other universities.

Core System

The core system of GAP has four parts.
1. A kernel, written in C, which gives memory management. A set of functions, operating on integers, fields, permutations. An interpreter for the GAP language. The language is, as you can probably guess, untyped, and supports some form of OO programming. Some system functions for handling IO etc, testing and debugging tools, and a REPL.
2. A large library of GAP functions. Users can also add their own functions.
3. A library of "Group Theoretical data". I am guessing this means it has some hardcoded data for small Groups, and also seems to have other data, e.g. character tables.
4. Documentation.

The Gap Website has a great deal of information about the GAP core system (here).

Groups

If you have any interest in Group Theory then playing around in GAP for a few minutes can be quite interesting. There are a large variety of inbuilt functions. For example, Lets start with a Cyclic Group (\(Cyc(6)\).

Group([ (1,2,3,4,5,6) ])
gap> Order(c6);
6
gap> IsAbelian(c6);
true
gap> IsSimple(c6);
false

Since Cyclic groups have a single generator, we only needed one permutation to generate (\(Cyc(6)\). Obviously it is abelian, and it is not simple, since (\(Cyc(2)\) and (\(Cyc(3)\) are normal subgroups.

Checking Isomorphism

It is possible to check whether two groups are isomorphic. Checking isomorphism gts complicated for larger and larger groups but an easy test case is to determine whether \(Cyc(4) \cong Cyc(2)\times Cyc(2)\) (Spoilers: they are not isomorphic).

gap> LoadPackage("sonata");
true
gap> c4 := Group((1,2,3,4));
Group([ (1,2,3,4) ])
gap> c2 := Group((1,2));
Group([ (1,2) ])
gap> c2xc2 := DirectProduct(c2,c2);
Group([ (1,2), (3,4) ])
gap> IsIsomorphicGroup(c2xc2,c4);
false

We loaded the "sonata" package, which contained the definition of the function IsIsomorphicGroup (see here).

Sporadic Simple Groups

Mathieu Groups

GAP has inbuilt support for generating well-known groups and Sporadic Simple Groups. The first discovered sporadic simple groups were the Mathieu groups. There are actually 5 true Mathieu groups - permutation groups on sets of size 11,12,22,23,24 respectively. GAP also includes groups acting on sets of size 9,10,21, which aren't strictly sporadic simple groups (e.g. the group \(M_{21}\) is actually a projective linear group, which can be generated from permutations of a steiner system \(S(2,5,21)\).
Regardless, we can generate these groups using the MathieuGroup function. Below, we generate \(M_{24}, M_{23}, M_{22}\) and also look at the stabilizer of a single point in the set of 24 points which \(M_{24}\) permutes, and the stabilizer of a two-point set. As it happens \(M_23\) is isomorphic to the stabilizer of a single point. \(M_{22}\) is isomorphic to the stabilizer of a single point in the stabilizer of a pair in \(M_{24}\). We cannot prove these, but we can at least see the orders of the groups are the correct size.

gap> m24 := MathieuGroup(24);
Group([ (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23), (3,17,
10,7,9)(4,13,14,19,5)(8,18,11,12,23)(15,20,22,21,16), (1,24)(2,23)(3,12)(4,16)
(5,18)(6,10)(7,20)(8,14)(9,21)(11,17)(13,22)(15,19) ])
gap> m23 := MathieuGroup(23);
Group([ (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23), (3,17,
10,7,9)(4,13,14,19,5)(8,18,11,12,23)(15,20,22,21,16) ])
gap> x := Stabilizer(m24, 1);
Group([ (3,17,10,7,9)(4,13,14,19,5)(8,18,11,12,23)(15,20,22,21,16), (2,24,16,
5,8)(4,22,21,15,17)(7,11,20,10,13)(12,18,19,23,14), (6,22,17)(8,11,13)
(9,15,21)(10,12,23)(14,20,18)(16,24,19) ])
gap> m22 := MathieuGroup(22);
Group([ (1,2,3,4,5,6,7,8,9,10,11)(12,13,14,15,16,17,18,19,20,21,22), (1,4,5,9,
3)(2,8,10,7,6)(12,15,16,20,14)(13,19,21,18,17), (1,21)(2,10,8,6)(3,13,4,17)
(5,19,9,18)(11,22)(12,14,16,20) ])
gap> y := Stabilizer(m24, (1,2));
<permutation group of size 887040 with 10 generators>
gap> Size(m23);
10200960
gap> Size(x);
10200960
gap> Size(m22);
443520
gap> Size(y);
887040

Orbits and Stabilizers

GAP has functions for calculating the orbits and stabilizers of permutations, acted on by a group.
Just to recall, the Orbit-Stabilizer Theorem states:
Let \(G,X\) be a group and a set on which the group acts, respectively.
For any \(x \in X\), the orbit of \(x\), \(Orb(x)\), that is, all the elements of \(X\) for which there is a group action of \(G\) mapping \(x\) to that element.
The stabilizer of some \(x \in X\), \(Stab(x)\), is the set of \(g \in G\) such that \(gx \rightarrow x\). i.e. the set of group elements which map \(x\) to itself.
Then \[ |Orb(x)| \times |Stab(x)| = |G|.\]

We can calculate orbits and stabilizers. For this example, let's use the Dihedral Group \(D_{8}\), the permutation group of a square.

gap> d8:= Group((1,3),(1,2,3,4));
Group([ (1,3), (1,2,3,4) ])
gap> Size(d8);
8
gap> Orbit(d8,(1,2));
[ (1,2), (2,3), (3,4), (1,4) ]

The Orbit of the pair \((1,2)\) is \((1,2), (2,3), (3,4), (1,4)\). Let's take a look at it's stabilizer.

gap> stab:=Stabilizer(d8,(1,2));
Group([ (1,2)(3,4) ])
gap> Size(stab);
2

We can confirm that the size of the orbit (4) multiplied by the size of the stabilizer (2) is indeed equal to the size of the group (8). Moving on from that trivial example, let's find the orbit of the permutation (1,2,3,4,5) in the Mathieu group \(M_{24}\).

gap> m24:=MathieuGroup(24);
gap> orbit:= Orbit(m24,(1,2,3,4,5));
gap> Size(orbit);
1020096
gap> stab:=Stabilizer(m24,(1,2,3,4,5));
<permutation group of size 240 with 4 generators>
gap> Size(orbit) * Size(stab) = Size(m24);
true

We know that \(M_{24}\) acts on a set of 24 points. What is the orbit of a set of a subset of those 24 points, of size 5, say?

gap> orb:= Orbit(m24,[1,2,3,4,5],OnSets);
gap> Size(orb);
42504

That is, the total number of 5-sets of a 24-set. i.e. \(M_{24}\) is a 5-transitive group; any 5 points are mapped to any other 5 points. (This is a consequence of \(M_{24}\) being transitive on the octads of the \(S(5,8,24)\) steiner system on which it acts.

That is it for the first part of this initial dive into GAP. I will write Part 2 soon, as there are many, many more things GAP is capable of.