Much of the HAP package is aimed at computations related to specific instances of the following.

A General Algebraic Problem

Let Z be an integral domain. Let Z[x₁,x₂,...,x_t] be the free associative ring over Z generated by x₁,...,x_t. Let A=Z[x₁,x₂,...,x_t]/J be a quotient algebra. Let M and N be A-modules. How can we calculate the modules

Tor^A_k(M,N) and Ext_A^k(M,N)

for integers k >=0?

Recall that these modules are defined in terms of a sequence of module homomorphisms

... ---> R₄ ---> R₂ ---> R₁ ---> R₀

such that

Such a sequence of module homomorphisms is said to be a free A-resolution of the module M.

Applying the functor Hom_A(-,N) to each module in the resolution R_* we obtain a sequence of induced module homomorphisms

dⁿ : Hom_A(R_n,N) ---> Hom_A(R_n+1,N) (n>=0).

The module Ext_A^k(M,N) is defined to be the homology module

Ext_A^k(M,N) = ker (d^k) / image (d^k-1)

with the convention d^-1=0. It can be shown that the isomorphism type of the module Ext_A^k(M,N) is unchanged if we change the choice of free resolution R_*.

The module Tor^A_k is defined analogously by tensoring each free module R_n with the module N over A, and taking homology of the resulting sequence of tensored modules.

In particular, HAP has functions aimed at the following.

Special Case.

Let Z be the ring of integers. Let G be a group. Let A=ZG be the group ring of G. Let M=Z be the ring of integers considered as a trivial ZG-module. Let N be an arbitrary ZG-module. The cohomology and homology of the group G are defined as

H^k(G,N) = Ext_ZG^k(Z,N) , H_k(G,N) = Tor^ZG_k(Z,N) .

The integral (co)homology of G is of particular interest and is defined to be the case where N equals the trivial module Z. The mod p (co)homology is a useful approximation to integral (co)homology and corresponds to letting N be the field Z_p of p elements with trivial action of G.

HAP also contains some functions aimed at the following.

A General Topological Problem

Let X be a bounded subspace of Euclidean space Rⁿ arising as a union of unit n-cubes whose vertices have integer coordinates. The subspace X might arise as a topological model of experimental data (such as a medical image) or it might be the more traditional kind of CW-complex studied in classical algebraic topology. How can we efficiently compute the cohomology groups (and possibly even some homotopy groups) of X ?

Representations

The typical HAP user does not need to know the precise details of how mathematical concepts are represented in HAP. However, a user who wishes to extend the HAP package will need such details.

Some of the concepts from homological algebra are represented in HAP using existing GAP data types (first table). Other concepts are represented using new gap data types (second table). For each of the new data types there is a boolean valued function IsHapNameOfDataType(X) .

HAP Representations using existing GAP data types

Free ZG-module (words)	Let eltsG be a (partial) listing of elements in some group G (which could be finite or infinite).  In order to represent a word w in a free ZG-module M of rank n we use a list of integer pairs w=[ [i1,g1], [i2,g2], ..., [ik,gk] ]. The integers ij lie in the range between -n and n and correspond to the free ZG-generators of M and their additive inverses. The integers gj are positive and correspond to the group element eltsG[gj]. The (partial) listing eltsG may contain duplicate copies of elements of G.
Additive Functor (Additive Contravariant Functor)	A functor T(X) is a function which inputs either a ZG-resolution X=R, or else an equivariant chain map between resolutions X=(f: ---> S) . If  X=R then T(R) is a chain complex. If X=(f:R ---> S) then T(X) is a chain map T(R) ---> T(S). (A contavariant functor is similar, except that T(R) is a cochain complex and T(R--->S) is a cochain map T(S) ---> T(R). )
Homology group (Cohomology group)	An homology group Hn(C) is a finitely generated abelian group and is represented by a list whose integer entries are the torsion coefficients of the group. A homomorphism Hn(C) ---> Hn(D) of homology groups is represented as a group homomorphism between finitely presented groups. (Cohomology groups and homomorphisms of cohomology groups are represented similarly.)
Homology vector space (Cohomology vector space)	When the ground ring Z is the field of p-elements or the rationals, then an homology group Hn(C) is actually a vector space and is thus represented by a single integer - the dimension of the vector space. (The prime p is omitted in this representation.) A homomorphism Hn(C) ---> Hn(D) of homology vector spaces is however represented as a group homomorphism between finitely presented groups. (Mod p cohomology groups and homomorphisms of cohomology groups are represented similarly.)
Mtx-module	A module over the mod p group ring FG of a finite group G can be represented using the standard GAP notion of "meat-axe" module. Such a module consists of a record M with components M.generators is a list of matrices over the field of p elements that generates a homomorphic image of G. M.gens is a list of generators of G corresponding to the matrices in M.generators. (This component is optional. In its abscence it is assumed that M.gens = M.generators). M.dimension is the dimension of the underlying vector space. M.field is the field F=GF(p) . M.isMTXModule is the boolean true. All modules in HAP are assumed to act on the left. (So care is needed because in GAP's standard meataxe functions the matrix action is assumed to be on the right. A left meataxe module can be converted to a right module by replacing generators with their transposes.)
Coxeter diagram	A Coxeter diagram is a finite graph (with at most one edge between a pair of vertices) whose edges are labelled by integers n>2 or n = infinity. The graph is represented as a list D = [L1, ... Lt] in which each term is itself a list Lk = [vk, [uk1,nk1], [uk2,nk2], ... [ukm,nkm]] such that vertex vk is conneconcatenationted to vertex ukj by an edge with label nkj. It is necessary and sufficient to list just those vertices ukj > vk. We set nkj=0 when the edge label is infinity.
Graph of Groups	A graph of groups is a finite graph (with at most one edge between a pair of vertices) whose vertices are labelled by groups and whose edges are labelled by pairs [f,g] of group monomorphisms f:S --->G, g:S ---> H with common source and with ranges G and H equal to the labels of the boundary vertices of the edge. Such a graph is represented as a list D = [L1, ... Lt] where each Li is either a group G or a pair of group monomorphisms [f,g]. Each group G arising as a term in the list, or as the range or source of a monomorphism in the list, must be such that HasName(G) is true. Furthermore, distinct groups must have dirrerent names.
Array	An array is defined recursively to be a list A=[A1,...,An] of arrays with equal dimension and array size. A no entry Ai is a list then the array is said to have dimension 1 and  array size n. In general: Dimension(A) =1 + Dimension(Ai). Array_Size(A) = Concatenation(Array_size(Ai),[n]).

HAP Representations involving new GAP data types

ZG-resolution	A ZG-resolution means a free ZG-resolution of the trivial ZG-module Z, where G is a group and Z is the ring of integers (or the ring of integers modulo p, or the ring of rationals). A ZG-resolution  ... ---> Mn ---> Mn-1 ---> ... ---> M1 ---> M0 → Z is represented by a component object R with the following components. R!.dimension(k) is a function which returns the ZG-rank of the module Mk. R!.boundary(k,j) is a function which returns the image in Mk-1 of the j-th free generator of Mk. R!.homotopy(k,[i,g]) is a function which returns the image in Mk+1, under a contracting homotopy Mk ---> Mk+1, of the element [[i,g]]  in Mk. (The elements [[i,g]] freely generate Mk as an abelian group.) For some resolutions a contracting homotopy is not constructed, in which case R!.homotopy is set equal to "fail". (For some resolutions a component R!.partialHomotopy(k,w) is available. This is a function which returns the preimage in Mk+1 of an arbitrary word w in the kernel of  Mk ---> Mk-1  .) R!.elts is a (partial) list of (possibly duplicate) elements in G. In some cases R!.elts is a pseudo list (see below) and not a list. R!.group is the group in question (and could be a permutation group, matrix group, finitely presented group etc.). R!.properties is a list of pairs ["name", value] where "name" is a string and value is a numerical or boolean value. Example pairs are:  ["length", n] which records that there are n terms in the resolution; ["characteristic", p] which records the characteristic of Z; ["reduced", true] which record that M0 is isomorphic to ZG; ["type","resolution"] which records the type of the object R. The operation IsHapResoluton(R) returns "true" for a resolution.
Non-free ZG-resolution	A non-free ZG-resolution is an exact sequence of ZG-modules ... ---> An ---> An-1 ---> ... ---> A1 ---> A0 → Z in which the modules are not necessarily free. We can represent such a sequence (non-uniquely) by first choosing free modules Mk mapping onto the Ak  and then lifting the homomorphisms to a sequence ... ---> Mn ---> Mn-1 ---> ... ---> M1 ---> M0  of homomorphisms of free ZG-modules. Note that in the lifted  sequence homomorphisms will not in general square to zero. A non-free ZG-resolution  ... ---> Mn ---> Mn-1 ---> ... ---> M1 ---> M0 → Z is represented by a component object R with the following components. R!.dimension(k) is a function which returns the ZG-rank of the module Mk. R!.boundary(k,j) is a function which returns the image in Mk-1 of the j-th free generator of Mk. R!.homotopy(k,[i,g]) is a function which returns the image in Mk+1, under a contracting homotopy Mk ---> Mk+1, of the element [[i,g]]  in Mk. (The elements [[i,g]] freely generate Mk as an abelian group.) For most non-free resolutions a contracting homotopy is not constructed, in which case R!.homotopy is set equal to "fail". R!.elts is a (partial) list of (possibly duplicate) elements in G. In some cases R!.elts is a pseudo list (see below) and not a list. R!.group is the group in question (and could be a permutation group, matrix group, finitely presented group etc.). R!.stabilizer(k,j) returns the subgroup of G consisting of those elements that fix, up to sign, the i-th free generator of Mk. R!.action(k,j,g) is a function which returns +1 or -1 according to how the group element Elts[g] acts on the "orientation" of the j-th free generator in dimension k. R!.properties is a list of pairs ["name", value] where "name" is a string and value is a numerical or boolean value. Example pairs are:  ["length", n] which records that there are n terms in the resolution; ["characteristic", p] which records the characteristic of Z; ["reduced", true] which record that M0 is isomorphic to ZG; ["type","resolution"] which records the type of the object R. The operation IsHapNonFreeResoluton(R) returns "true" for a non-free resolution.
Equivariant chain map	An equivariant chain mapping f : R ---> S from a ZG-resolution to a ZG'-resolution is represented by a component object F with the following components. F!.source is the ZG-resolution R. F!.target is the ZG'-resolution S. F!.mapping(w,k) is a function which returns the image in Sk, under the chain map, of the element w=[ [i1,g1], [i2,g2], ..., [ik,gk] ]  in Rk. F!.properties is a list of pairs such as ["type", "equivariantChainMap"]. The operation IsHapEquivariantChainMap(F) returns "true" for an equivariant chain map F.
Chain complex (Cochain complex)	A chain complex means a chain complex of free Z-modules. A chain complex  ... ---> Cn ---> Cn-1 ---> ... ---> C1 ---> C0  is represented by a record C with the following components. C!.dimension(k) is a function which returns the Z-rank of the module Ck. C!.boundary(k,j) is a function which returns the image in Ck-1 of the j-th free generator of Ck. (Elements in Ck-1 are represented in the obvious was as vectors of length equal to the rank of Ck-1.) C!.properties is a list of pairs ["name",value] where "name" is a string and value is a numerical or boolean value. Example pairs are:  ["length", n] which would record that there are n terms in the chain complex; ["characteristic", p] which would record the characteristic of Z. The operation IsHapChainComplex(C) returns "true" for a chain complex C. (A cochain complex  ... <--- Cn <--- Cn-1 <--- ... <--- C1 <--- C0  is represented by a similar record C.  The difference is that C!.boundary(k,j) returns an element in Ck+1.)
Chain map (Cochain map)	A chain mapping f : C ---> D between chain complexes is a component object F with the following components. F!.source is the chain complex C. F!.target is the chain complex D. F!.mapping(v,k) is a function which returns the image in Dk, under the chain map, of a vector v in Ck. F!.properties is a list of pairs such as ["type", "chainMap"]. The operation IsHapEquivariantChainMap(F) returns "true" for a chain map F. (A cochain mapping is represented by a similar record.)
Filtered chain compex	A filtered chain complex means a sequence F0C < ... < Ft-1C < FtC of inclusions of chain complexes. We call the integer t the filtration length. A filtered chain complex is represented as a chain complex C with an additional component and property: C!.filteredDimension(r,n) is a function which gives the number of free generators in degree n of the chain complex FrC. Generators are usually ordered such that the first k generators of FrCn are also the first k generators of  FsCn for all s>r and all k; in this case C!.properties contains the pair ["initial_inclusion",true]. Sometimes generators are ordered such that the last k generators of FrCn are also the last k generators of  FsCn for all s>r and all k; in this case C!.properties contains the pair ["initial_inclusion",false]. C!.properties contains the pair ["filtration_length",t] . The operations IsHapFilteredChainComplex(C) and IsHapChainComplex(C) both return "true".
FpG-module	For a finite group G, and the field F of p elements, a submodule of the free FG-module FGn is represented by a component object M with the following components: M!.group is the finite group G, M!.characteristic is the prime p, M!.matrix is an echelon matrix whose rows form a basis for the underlying vector space, M!.action(g,M) is a function that inputs an element g in G and a matrix M whose rows are vectors in the vector space Fn|G| of dimenion any multiple of |G|. It returns the matrix got from M by letting g act on columns. M!.dimension is the dimension of the underlying vector space. M!.ambientDimension is n|G| . The operation IsHapFPGModule(M) returns "true" for an FpG-module M.
FpG-module homomorphism	A homomorphism Phi:M ---> N of FpG-modules (over a common group G and field F)  is a component object with the following components: Phi!.source is the source module M. Phi!.target is the target module N. Phi!.matrix is a matrix A over the field F whose rows are the images in N of those minimal generators of M produced using the function GeneratorsOfFpGModule(M). The operation IsHapFPGModuleHomomorphism(Phi) returns "true" for an FpG-module homomorphism Phi.
G-outer group	We'll say that a group N is a G-outer group if there is an associated function alpha:G ---> Aut(N) which induces a homomorphism G ---> Out(N).  A G-outer group is represented as a component object A with the following components: A!.ActingGroup is the group G. A!.ActedGroup is the group N. A!.OuterAction is a function which, to each g in G and each n in N, returns an element A!.OuterAction(g,n) in N. The following two mathematical properties hold. (1) For each g in G the function A!.OuterAction(g,_):N ---> N is an automorphism. (2) The function g---> A!.OuterAction(g,_) induces a homomorphism G ---> Out(N).  The operation IsGOuterGroup(M) returns "true" for a G-outer group M. Note that a G-module N can be viewed as a G-outer group N for which IsAbelian(N) returns the value True. For conveninece we'll often refer to an abelian G-outer group as a G-module.
G-outer group homomorphism	A homomorphism Phi:M ---> N of G-outer groups (over a common group G)  is a component object with the following components: Phi!.Source is the source G-outer group. Phi!.Target is the target G-outer group. Phi!. Mapping is a GAP group homomorphism from the underlying group of M to the underlying group of N. The operation IsGOuterGroupHomomorphism(Phi) returns "true" for a G-outer group homomorphism Phi.
G-complex (G-cocomplex)	A G-complex is a sequence ... ---> Cn ---> Cn-1 ---> ... ---> C1 ---> C0 of G-outer group homomorphisms over a common group G such that Image(Cn ---> Cn-1) is  a normal G-invariant subgroup of Kernel(Cn-1 ---> Cn-2). In particular, when each Cn is abelian it is a chain complex of G-modules. It is represented by a component object C with the following components: C!.boundary(n) is a function which returns the homomorphism Cn ---> Cn-1 for n>0. C!.properties is a list of pairs ["name",value] where "name" is a string and value is a numerical or boolean value. Example pairs are:  ["length", n] which would record that there are n terms in the chain complex. The operation IsHapGComplex(C) returns "true" for a G-complex C. (A G-cocomplex  ... <--- Cn <--- Cn-1 <--- ... <--- C1 <--- C0  is represented by a similar record C.  The difference is that C!.boundary(n) is a map Cn --> Cn+1.)
Simplicial Group	A simplicial group is represented by a component object G with the following components: G!.groupsList is a list [G0, G1, ...] of the groups in each degree up to some given degree n. G!.boundariesList is a list [D1, D2, ...] where Dk is a list of the k+1 boundary homomorphisms Gk --> Gk-1. G!.degeneraciesList is a list [S0, S1, ...] where Sk is a list of the k+1 degeneracy homomorphisms Gk --> Gk+1. G!.properties is a list of pairs ["name",value] where "name" is a string and value is a numerical or boolean value.  The operation IsHapSimplicialGroup(G) returns "true" for a simplicial group G.
Standard N-cocycle	A standard N-cocycle f:G×G×...×G ---> M of a group G with coefficients in an abelian G-outer group M (i.e. a G-module M) is represented as a component object F with the following components: F!.Module is the G-module M. F!.Arity is the integer N. F!.Mapping is a function which, for all g1 ,...,, gN in G, returns an element F!.Mapping(g1,g2,...,gN) in M. The function satisfies the N-cocycle condition. The operation IsStandardNCocycle(F) returns "true" for a standard N-cocycle.
Cat-1-group	A cat-1-group is a group endowed with a compatible category composition. It can be viewed as a group G with endomorphisms s,t:G-->G satisfying ss=s, ts=s, tt=t, st=t and [Ker(s),Ker(t)]=1. It is represented as a component object C with the following components. C!.sourceMap is the group homomorphism s:G-->G. C!.targetMap is the group homomorphism t:G->G. The operation IsHapCatOneGroup(C) returns "true" for a cat-1-group C.
Pure Cubical Complex	In HAP we use the term "pure cubical complex" to mean a subspace of Euclidean n-space Rn arising as a union of unit n-cubes whose vertices have integer coordinates. Such a space is represented by a component object T having two components: T!.binaryArray is a list [b1, ... ,bn] where the bi are binary array with common  dimension and array size. (See below for the definition of these terms.) T!.properties is a list of pairs such as ["dimension",2], ["arraySize",[256,512] . A binary array of dimension 1 is just a list b=[x1, ..., xn] where each xi is either 0 or 1. The array size of b is defined to be  [n] . A binary array of dimension d>1 is a list b=[x1, ..., xn] where each xi is a binary array of dimension d-1 and all xi have the same array size. The array size of b is defined to be the list of integers got by appending n to the array size of any xi. The operation IsHapPureCubicalComplex(T) returns "true" for a pure cubical complex T.
Filtered pure cubical complex	A filtered pure cubical complex is a pure cubical complex M with an additional component M!.filtration is an array of non-negative integers of the same dimension as M!.binaryArray. The entry M!.filtration[x] is less than or equal to t if and only if the t-th term Mt of the filtration on M has Mt!.binaryArray[x]=1 . The operations IsHapPureCubicalComplex(M) and IsHapFilteredPureCubicalComplex(M) returns "true" for a pure cubical complex M.
Cubical Complex	In HAP we use the term "cubical complex" to mean a cellular subspace of Euclidean n-space Rn arising as a union of open unit m-cubes of varying degrees whose centres have integer coordinates. Such a space is represented by a component object T having two components: T!.binaryArray is a list [b1, ... ,bn] where the bi are binary array with common  dimension and array size. (See above for the definition of these terms.) T!.properties is a list of pairs such as ["dimension",2], ["arraySize",[256,512] . Each entry "1" in the array corresponds to a cell with centre represented by the entry's coordinates. If all coordinates are odd then the cell is a vertex. If all coordinates are even then the cell is an n-cube. The operation IsHapCubicalComplex(T) returns "true" for a cubical complex T.
Filtered cubical complex	A filtered cubical complex is a cubical complex M with an additional component M!.filtration is an array of non-negative integers of the same dimension as M!.binaryArray. The entry M!.filtration[x] is less than or equal to t if and only if the t-th term Mt of the filtration on M has Mt!.binaryArray[x]=1 . The operations IsHapCubicalComplex(M) and IsHapFilteredCubicalComplex(M) returns "true" for a cubical complex M.
Cubical Complex  with Vector Field	A discret vector field on a cubical complex T is represented by adding the following two components to T: T!.vectors is an array with the same dimensions as T!.binaryArray. Let x be  the coordinate vector of an array position. We set T!.vectors[x]=0 iif the cell with coordinate vector x is critical.  We set T!.vectors[x]=y if there is a vector starting at the cell with coordinates x and ending at the cell with coordinates y. T!.rewrite(w) is a function which inputs a list w=[x1, ..., xk] of coordinate vectors of cells. It returns a list [y1, ..., ym] of the coordinate vectors of those critical cells to which the input cells w get  homotopied.
Simplicial Complex	A simplicial complex is represented by a component object T with the following components: T!.vertices is the list of vertices. T!.simplices(n,i) is a function that returns the list of vertices in the i-th n-simplex. T!.nrSimplices(n) is a function which returns the number of n-dimensional simplices. T!.enumeratedSimplex(v) is a function which inputs a list v of vertices representing an n-simplex and returns the position of this simplex in the list of all n-simplices. T!.properties  is a list of pairs such as ["dimension",2] . The operation IsHapSimplicialComplex(T) returns "true" for a simplicial complex T.
Regular CW-Complex	A regular CW-complex is represented by a component object Y with the following components: Y!.boundaries[n+1][k] is a list of integers [t,a1,...,at] where ai denote the (n-1)-dimensional cells in the boundary of the k-th cell of dimension n. Y!.coboundaries[n+1][k] is a list of integers [t,a1,...,at] where ai denote the (n+1)-dimensional cells in the coboundary of the k-th cell of dimension n. Y!.nrCells(n) is a function returning the number of cells in dimension n. Y!.properties is a list of properties. The following optional components may also be present (or else present but set equal to fail): Y!.vectorField[n][k] is either unbound or equal to an integer k' . The latter case represents a "flow" from the k-th cell of dimension n to the k'-th cell of dimension n-1. Y!.inverseVectorField[n][k'] is either unbound or equal to an integer k . The latter case represents a "flow" from the k-th cell of dimension n to the k'-th cell of dimension n-1. Y!.criticalCells is a list of pairs [n,k] representing the fact that the k-th cell in dimension n is critical (i.e. is not involved in any flow). Y!.orientation[n][k] is a list of the incidence numbers of the cells in the boundary of the k-th cell of dimension n. So Y!.orientation[n][k][j] is the incidence number (+1 or -1) of the j-th cell in the boundary. The operation IsHapRegularCWComplex(Y) returns "true" for a regular CW-complex Y.
Pseudo list	A pseudolist L has the same basic functionality as that of a list except that: Position(L,x) uses a binary search rather than a linear search. The elements in L must be distinct. Add(L,x) returns a pseudolist with last entry equal to x. Not all list functions and methods apply to L.
Sparse matrix	A sparse matrix is a component object M with the following components: M!.mat is a list of lists. The entries in M!.mat[i] are pairs of integers [j,k] denoting that the represented matrix has entry k in the i-th row and j-th column. M!.characteristic denotes the characteristic of the field from which the matrix entries are taken M!.rows is the integer number of rows in the matrix. M!.cols is the integer number of columns in the matrix. The operation IsHapSparseMat(M) returns "true" for a sparse matrix M.
Sparse chain complex	A sparse chain complex means a chain complex of free Z-modules. A sparse chain complex  ... ---> Cn ---> Cn-1 ---> ... ---> C1 ---> C0  is represented by a record C with the following components. C!.dimension(k) is a function which returns the Z-rank of the module Ck. C!.boundary(k,j) is a function which returns the image in Ck-1 of the j-th free generator of Ck. (Elements in Ck-1 are represented in the obvious way as sparse vectors of length equal to the rank of Ck-1.) C!.properties is a list of pairs ["name",value] where "name" is a string and value is a numerical or boolean value. Example pairs are:  ["length", n] which would record that there are n terms in the chain complex; ["characteristic", p] which would record the characteristic of Z. The operation IsHapSparseChainComplex(C) returns "true" for a sparse chain complex C.