GAP (computer algebra system)

This article is about a software package. For other uses, see Gap (disambiguation).

GAP

Developer(s)	University of St Andrews RWTH Aachen TU Braunschweig Colorado State University TU Kaiserslautern
Initial release	1988
Stable release	4.14.0 / 5 December 2024 (5 December 2024)
Repository	github.com/gap-system/gap
Written in	C
Operating system	Cross-platform
Type	Computer algebra system
License	GNU General Public License
Website	www.gap-system.org

GAP (Groups, Algorithms and Programming) is an open source computer algebra system for computational discrete algebra with particular emphasis on computational group theory.

History

GAP was developed at Lehrstuhl D für Mathematik (LDFM), Rheinisch-Westfälische Technische Hochschule Aachen, Germany from 1986 to 1997. After the retirement of Joachim Neubüser from the chair of LDFM, the development and maintenance of GAP was coordinated by the School of Mathematical and Computational Sciences at the University of St Andrews, Scotland. In the summer of 2005 coordination was transferred to an equal partnership of four 'GAP Centres', located at the University of St Andrews, RWTH Aachen, Technische Universität Braunschweig, and Colorado State University at Fort Collins; in April 2020, a fifth GAP Centre located at the TU Kaiserslautern was added.

Features

GAP contains a procedural programming language and a large collection of functions to create and manipulate various mathematical objects. It supports integers and rational numbers of arbitrary size, memory permitting. Finite groups can be defined as groups of permutations and it is also possible to define finitely presented groups by specifying generators and relations. Several databases of important finite groups are included. GAP also allows to work with matrices and with finite fields (which are represented using Conway polynomials). Rings, modules and Lie algebras are also supported.

Distribution

GAP and its sources, including packages (sets of user contributed programs), data library (including a list of small groups) and the manual, are distributed freely, subject to "copyleft" conditions. GAP runs on any Unix system, under Windows, and on Macintosh systems. The standard distribution requires about 300 MB (about 400 MB if all the packages are loaded).

The user contributed packages are an important feature of the system, adding a great deal of functionality. GAP offers package authors the opportunity to submit these packages for a process of peer review, hopefully improving the quality of the final packages, and providing recognition akin to an academic publication for their authors. As of March 2021, there are 151 packages distributed with GAP, of which approximately 71 have been through this process.

An interface is available for using the SINGULAR computer algebra system from within GAP. GAP is also included in the mathematical software system SageMath.

Sample session

Permutation group

gap> G:=SmallGroup(8,1); # Set G to be the 1st group (in GAP catalogue) of order 8.
<pc group of size 8 with 3 generators>
gap> i:=IsomorphismPermGroup(G); # Find an isomorphism from G to a group of permutations.
<action isomorphism>
gap> Image(i,G); # Generators for the image of G under i - written as products of disjoint cyclic permutations.
Group([ (1,5,3,7,2,6,4,8), (1,3,2,4)(5,7,6,8), (1,2)(3,4)(5,6)(7,8) ])
gap> Elements(Image(i,G)); # All the elements of im G.
[ (), (1,2)(3,4)(5,6)(7,8), (1,3,2,4)(5,7,6,8), (1,4,2,3)(5,8,6,7),
  (1,5,3,7,2,6,4,8), (1,6,3,8,2,5,4,7), (1,7,4,5,2,8,3,6), (1,8,4,6,2,7,3,5) ]

Euclidean ring

gap> # test consistency of EuclideanDegree, EuclideanQuotient, EuclideanRemainder,
gap> # and QuotientRemainder for some ring and elements of it
gap> checkEuclideanRing :=
> function(R, colls...)
>   local coll1, coll2, a, b, deg_b, deg_r, q, r, qr;
>   if Length(colls) >= 1 then coll1:=colls[1];
>   elif Size(R) <= 100 then coll1 := R;
>   else coll1 := List([1..100],i->Random(R));
>   fi;
>   if Length(colls) >= 2 then coll2:=colls[2];
>   elif Size(R) <= 100 then coll2 := R;
>   else coll2 := List([1..100],i->Random(R));
>   fi;
>   for b in coll1 do
>     if IsZero(b) then continue; fi;
>     deg_b := EuclideanDegree(R, b);
>     for a in coll2 do
>       q := EuclideanQuotient(R, a, b); Assert(0, q in R);
>       r := EuclideanRemainder(R, a, b); Assert(0, r in R);
>       if a <> q*b + r then Error("a <> q*b + r for ", [R,a,b]); fi;
>       deg_r := EuclideanDegree(R, r);
>       if not IsZero(r) and deg_r >= deg_b then Error("Euclidean degree did not decrease for ",[R,a,b]); fi;
>       qr := QuotientRemainder(R, a, b);
>       if qr <> [q, r] then Error("QuotientRemainder inconsistent for ", [R,a,b]); fi;
>     od;
>   od;
>   return true;
> end;;

gap> # rings in characteristic 0
gap> checkEuclideanRing(Integers,[-100..100],[-100..100]);
true
gap> checkEuclideanRing(Rationals);
true
gap> checkEuclideanRing(GaussianIntegers);
true
gap> checkEuclideanRing(GaussianRationals);
true

gap> # finite fields
gap> ForAll(Filtered([2..50], IsPrimePowerInt), q->checkEuclideanRing(GF(q)));
true

gap> # ZmodnZ
gap> ForAll([1..50], m -> checkEuclideanRing(Integers mod m));
true
gap> checkEuclideanRing(Integers mod ((2*3*5)^2));
true
gap> checkEuclideanRing(Integers mod ((2*3*5)^3));
true
gap> checkEuclideanRing(Integers mod ((2*3*5*7)^2));
true
gap> checkEuclideanRing(Integers mod ((2*3*5*7)^3));
true

See also

• Comparison of computer algebra systems

External links

• Official website
• Gap-system on GitHub