GAP

A few in my department have asked about GAP recently. This page is designed to be somewhere they and others may find basic information. GAP is an open-source computer algebra system (the acronym stands for Groups, Algorithms, Programming) with a particular emphasis on computational group theory.

Obtaining GAP

If you use a reasonably well-equipped Linux distribution (e.g., Ubuntu, Debian, etc.) then GAP is most likely already in your program repository. For example, on Ubuntu one may install GAP by issuing the command

$ sudo apt-get install gap-core

The repository version is usually up-to-date for GAP. However, you may want more manual control over the installation. For other options (including other operating systems, pre-compiled binaries, and source code that you may compile yourself) see here.

Learning GAP

The GAP tutorial is a good place to start. After you are familiar with GAP, you will find the reference documentation to be helpful. Keep in mind that GAP has its own internal language. It does take some time, although in my opinion not much time, to learn.

Why GAP?

The question I am most frequently asked about GAP is along the lines of: "Why would someone use GAP instead of Sage?" To answer this, I'll start with a very basic example and then explain the consequences a bit. Let's create a permutation group G by transposing two integers. First, we do it in GAP.

gap> G:=Group([(99,100)]);

Now, we create the same group in Sage.

sage: G=PermutationGroup([[(99,100)]])

In my mind, this group is obviously transitive and obviously primitive. GAP agrees. Sage does not.

gap> IsTransitive(G);
true
gap> IsPrimitive(G);
true
sage: G.is_transitive()
False

The reason for this is that GAP views the domain for G as the set [99,100] while Sage views the domain as [1,2,...,100]. I would argue that Sage is mathematically incorrect here, as no definition of "permutation group" I have ever seen states that the underlying set must respect a well-ordering. (Actually, the only reason we find it convenient to use integers for permutation representations is because we won't run out of them. Which integers one uses is of no importance.) Many permutation group algorithms (e.g., backtrack) do place well-orders on the underlying set of a permutation representation at runtime, but that order is very rarely the natural one and is directly inherited from the representation itself.

One may think that defining a permutation group on integers that are as small as possible will solve the problem. For instance, the above cyclic group of order 2 could simply be defined with the transposition (1,2) instead of (99,100). This won't solve the issue. For example, create a symmetric group of degree n acting on [1,2,...,n]. If we consider a random point stabilizer in this symmetric group, we then have a group isomorphic to the symmetric group of degree n-1 which stabilizes some point in [1,2,...,n]. In GAP, the degree of this point stabilizer will always be n-1 and the point stabilizer itself will always act transitively on its domain. In Sage, there is a (n-1)/n probability that the point stabilizer will act transitively and only a 1-(n-1)/n probability that it will be of degree smaller than the original group (although by definition it acts on fewer points!). That's just silly. For reasons like this, I use GAP.

The complication here is that Sage uses GAP for many of its group theory calculations. (A copy of GAP is included inside Sage.) The main problem is that GAP and Sage view permutation groups fundamentally differently. GAP's view is a bit more mature and mathematically rigorous, in my opinion. With that said, I do use Sage a lot for other purposes (educational applications in the classroom, combinatorics with sage-combinat, etc.).

And then there is Magma. Don't ask me about Magma unless you plan to give me a copy of Magma and allow me to examine, pull apart, and use or re-write the source.

© 2011 Jason B. Hill. All Rights Reserved.