After a two-week hiatus, we’re back with another installment of FSR. This week we look at GAP (Groups, Algorithms, Programming), a “system for computational discrete algebra, with particular emphasis on Computational Group Theory”. GAP is another freebie, and it has a very large user community that has produced dozens of add-on packages to increase its functionality.
One of my favorite things about GAP is the transparency of the commands. For example, if you want to construct the natural homomorphism from a vector space V to the quotient space V/W, the command is NaturalHomomorphismBySubspace(V,W). If you don’t know the command for a particular function, you can make a decent guess by just typing what the function does (e.g., Factorial, IsPrime).
I first encountered GAP in an independent study course in group theory while in graduate school. At that time I needed to compute character tables for a lot of groups, and since the “G” in GAP stands for “Groups”, I thought, “Why not?” I ended up writing a program to compute adjacency matrices for representation graphs for my master’s thesis:
rep := function ( tbl ) local i, n, tnsr; n := Length( SizesConjugacyClasses( tbl ) ); for i in [ 1 .. n ] do tnsr := Tensored( [ Irr( tbl )[i] ], Irr( tbl ) ); Print( MatScalarProducts( tbl, Irr( tbl ), tnsr ), "\n" ); od; end;
This very short program generates the adjacency matrices for all irreducible representation graphs of a finite group. It was easy to write, and it allowed me to generate enough examples to make conjectures and prove results.
Another great, fun example of GAP’s abilities is analyzing the symmetry group of a Rubik Cube (not to be confused with a Rubik hypercube). If we number the 48 movable faces of the 27 cubes, then the symmetry group is generated by the six permutations corresponding to a 90° rotation of each of the six (full) faces. GAP can handle this quite easily:
gap> cube := Group( > ( 1, 3, 8, 6)( 2, 5, 7, 4)( 9,33,25,17)(10,34,26,18)(11,35,27,19), > ( 9,11,16,14)(10,13,15,12)( 1,17,41,40)( 4,20,44,37)( 6,22,46,35), > (17,19,24,22)(18,21,23,20)( 6,25,43,16)( 7,28,42,13)( 8,30,41,11), > (25,27,32,30)(26,29,31,28)( 3,38,43,19)( 5,36,45,21)( 8,33,48,24), > (33,35,40,38)(34,37,39,36)( 3, 9,46,32)( 2,12,47,29)( 1,14,48,27), > (41,43,48,46)(42,45,47,44)(14,22,30,38)(15,23,31,39)(16,24,32,40) ); <permutation group with 6 generators>
Want to know how big this is? That is, how many different configurations are there for the cube?
gap> Size( cube ); 43252003274489856000
That’s 43.25 quintillion! According to John Allen Paulos, in his book Innumeracy,
Ideal Toy Company stated on the package of the original Rubik cube that there were more than three billion possible states the cube could attain. It’s analogous to Mac Donald’s proudly announcing that they’ve sold more than 120 hamburgers.
Much more on this example can be found here.
The only downside to GAP is the potential overhead needed to get it up and running. GAP is a hefty program, requiring over 500MB of disk space, and the download speed from the official site can be slow. Some of the optional packages are rather large, too. It runs almost out of the box on Windows (since you get a precompiled version), but on Unix/Linux-based systems, you’ll have to compile it yourself, and it can take a fair amount of tweaking to get it going. Also, some packages only work in a Unix-like environment, so if you use the Windows version, you’re better off getting Cygwin and compiling GAP from scratch.
I don’t use GAP as much as other CAS programs, but whenever I need to do group or vector space computations, it’s my first choice. I’ve also started using it as a replacement for Magma (not free), which I no longer have access to. I don’t think GAP’s appeal is as broad as something like Maxima (review), but there are plenty of cool things you can do with it.