HAP home

HAP REPRESENTATIONS AND DATA TYPES

The HAP package is aimed at computations related to very specific instances of the following general problem.

General Problem

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

TorAk(M,N) and ExtAk(M,N)

for integers k >=0?

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

... ---> R4 ---> R2 ---> R1 ---> R0

such that

  • (Freeness) Each Rn is a free A-module.
  • (Exactness) The image of Rn+1 ---> Rn equals the kernel of Rn ---> Rn-1 for all n>0.
  • (Augmentation) The cokernel of R1 ---> R0 is isomorphic to the module M.
  • Such a sequence of module homomorphisms is said to be a free A-resolution of the module M.

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

    dn : HomA(Rn,N) ---> HomA(Rn+1,N) (n>=0).

    The module ExtAk(M,N) is defined to be the homology module

    ExtAk(M,N) = ker (dk) / image (dk-1)

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

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

    The long term aim is for HAP to handle a range of specific instances of the above problem. Initially, many of the HAP data types and functions are aimed at the following special case.

    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

    Hk(G,N) = ExtZGk(Z,N) ,
    Hk(G,N) = TorZGk(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 Zp of p elements with trivial action of G.

    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 connected 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.


    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.
    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 ---> Cis 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 <--- Cis 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.)
    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.
    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.