GAP 4.8.9 installation with standard packages -- copy to your CoCalc project to get it
#(C) Irina Kholodna, 2001 (converted to HAP format by Graham Ellis)
#####################################################################
InstallGlobalFunction(ResolutionSmallFpGroup,
function(arg)
local
G,n,
table,
Table,
NullList,
LastFactor,
WordsToIntegers,
Der,
IntegersToWords,
VectorPermutations,
GenerateAsZGModule,
FoxMatrix,
Is_ZLinearComb,
MinimalModuleGenerators,
IdentityModuleZBasis,
IdentityModuleGenerators,
Resolution,
IrinasRes,
ExtendIrinasRes,
Dimension,
Boundary,
EltsG, OrderG,
Int2Pair,
FoxM,
Charact,
FpToPerm,
pG;
G:=arg[1];
n:=arg[2];
if Length(arg)>2 then Charact:=arg[3]; else Charact:=0; fi;
OrderG:=Order(G);
FpToPerm:=IsomorphismPermGroup(G);
pG:=Image(FpToPerm);
EltsG:=List(Elements(pG),x->PreImagesRepresentative(FpToPerm,x));
########################START OF IRINA'S CODE #######################
#####################################################################
# GAP V.4 FUNCTIONS FOR COMPUTING THE MODULE OF IDENTITIES AND THE LOW-
# DIMENSIONAL HOMOLOGY OF A FINITELY PRESENTED GROUP
# (Written by Irina Kholodna)
# This file contains GAP V.4 functions for computing the module of
# identities of a finite presentation of a finite group G, and for
# computing a free ZG-resolution.
# For all the functions:
# by **the list of records representing an element zg in
# ZG+...+ZG (k copies of ZG)**
# we mean the constraction that becomes clear if we consider
# the following example.
# Let G has a presentation <x, y| x^2, y^2, (x*y)^2>.
# The command Elements(G) gives the list [1, x, y, xy].
# Let zg be an element in the free module ZG+ZG, e.g.
# zg=(x+y+2xy)e1+(x+3y)e2.
# **The list of records representing this element** is:
# [ [ rec(coeff:=1, word:=x),
# rec(coeff:=1, word:=y),
# rec(coeff:=2, word:=xy) ],
# [ rec(coeff:=1, word:=x,
# rec(coeff:=3, word:=y) ] ]
#_____________________GLOBAL__VARIABLE__________________________
table:=[];
#---------------------------------------------------------------
#***************************************************************
Table:=function(G)
#***************************************************************
# Given a finite group G, this function constracts
# a square s x s matrix (where s = Size(G)) in the following way.
# Let g_i = Elements(G)[i], and [n_1, n_2, ..., n_s] is the
# list of integers representing an element z in ZG in the usual
# way. Then the ith row [m_1, m_2, ..., m_s] of the matrix
# is a list of integers such that [n_(m_1), n_(m_2), ..., n_(m_s)]
# represents g_i*z.
local #pG,
product, permutation, index,
i, z, pg;
table:=[];
#pG:=Image(IsomorphismPermGroup(G));
for pg in Elements(pG) do
product:=[];
for z in Elements(pG) do
Add(product,Position(Elements(pG), pg*z));
od;
permutation:=MappingPermListList(product,[1..Size(pG)]);
index:=[];
for i in [1..Size(pG)] do
Add(index,i^permutation);
od;
Add(table,index);
od;
end;
#***************************************************************
NullList:=function(k)
#***************************************************************
local i, list;
list:=[];
for i in [1..k] do
list[i]:=0;
od;
return list;
end;
#***************************************************************
LastFactor:=function(G,w)
#***************************************************************
# Given a finitely presented group G and a word w
# in terms of generators of G, this function returns
# the extreme right letter in this word.
local z, d;
for z in FreeGeneratorsOfFpGroup(G) do
d:=w*z^-1;
if d<w
then return z;
else d:=w*z;
if d<w
then return z^-1;
fi;
fi;
od;
end;
#***************************************************************
WordsToIntegers:=function(G,zg)
#***************************************************************
# Given a finite group G and the list of records zg (IN FREE GENERATORS!)
# representing an element in ZG, this
# function returns the integer vector of length |G|
# corresponding to this element.
local #FpToPerm, #pG,
position, l,
d, i;
#FpToPerm:=IsomorphismPermGroup(G);
#pG:=Image(FpToPerm);
l:=NullList(Size(pG));
for d in zg do
d.word:=MappedWord(d.word,FreeGeneratorsOfFpGroup(G),GeneratorsOfGroup(G));
position:=Position(Elements(pG),d.word^FpToPerm);
l[position]:=l[position]+d.coeff;
od;
return l;
end;
#***************************************************************
Der:=function(G,w,i)
#***************************************************************
# Given a finitely presented group G, a word w in terms of
# freee generators of F:=FreeGroupOfFpGroup(G) and integer number i
# (0 < i < |FreeGeneratorsOfFpGroup(G)|+1), this function returns an
# integer list representing (as an element in ZG) the Fox derivative
# of w with respect to the generator of F whose position in the list
# of generators is i.
local F,
d, rem, apply;
F:=FreeGroupOfFpGroup(G);
apply:=function(F,w,i,rem)
local l, next, item;
if Length(w)=1
then if w<>GeneratorsOfGroup(F)[i] and w<>GeneratorsOfGroup(F)[i]^-1
then return rec(coeff:=0, word:=[]);
else if w=GeneratorsOfGroup(F)[i]
then return rec(coeff:=1, word:=One(F));
else return rec(coeff:=-1, word:=w);
fi;
fi;
fi;
l:=LastFactor(F,w);
w:=w*l^-1;
item:=rec(coeff:=apply(F,l,i,rem).coeff,
word:=w*apply(F,l,i,rem).word);
if item.word<>[]
then Add(rem, item);
fi;
next:=apply(F,w,i,rem);
return next;
end;
rem:=[];
d:=apply(F,w,i,rem);
if d.word<>[]
then Add(rem,d);
fi;
return WordsToIntegers(G,rem);
end;
#***************************************************************
IntegersToWords:=function(G,v)
#***************************************************************
# Given a finite group G and an integer vector v whose
# length |v| is an integer multiple of the order of G,
# this function constract the list of records representing
# the corresponding (in the usual way) element in
# ZG+...+ZG (|v|/|G| copies).
local zg,
k, l,
i, j;
k:=Length(v)/Size(G);
zg:=[];
for i in [1..k] do
zg[i]:=[];
l:=0;
for j in [Size(G)*(i-1)+1..Size(G)*i] do
l:=l+1;
if v[j]<>0
then Add(zg[i], rec(coeff:=v[j],
word:=EltsG[l]));
fi;
od;
od;
return zg;
end;
#***************************************************************
VectorPermutations:=function(G, v)
#***************************************************************
# Given a finite group G and an integer
# vector v whose length |v| is an integer multiple of the
# order of G, this function returns a list of integer
# vectors U={u_i | i=1,...,|G|} by permuting the coordinates
# of v as follows. The vector v is identified in the usual
# way with an element in the free module ZG+...+ZG
# (|v|/|G| copies of ZG). The vector u_i represents the
# element g_i*v in this module (where {g_i | i=1,...,|G|}
# is the set of elements of G.
local #pG,
k, U,
Index, i, j;
#pG:=Image(IsomorphismPermGroup(G));
k:=Size(v)/Size(pG);
U:=[];
for j in [1..Size(pG)] do
Index:=StructuralCopy(table[j]);
for i in [1..k-1] do
Append(Index, table[j]+i*Size(pG));
od;
Add(U,v{Index});
od;
return U;
end;
#***************************************************************
GenerateAsZGModule:=function(G,V)
#***************************************************************
local products, v;
products:=[];
for v in V do
Append(products, VectorPermutations(G, v));
od;
return products;
end;
#***************************************************************
FoxMatrix:=function(G)
#***************************************************************
# Given a finitely presented finite group G=<X|R>, the command
# A:=FoxMat(G);
# constructs the integer matrix A representing the homomorphism
# delta: C2 --> C1,
# where C2 is the direct sum ZG+ZG+...+ZG (|R| copies of ZG),
# C1 is the direct sum ZG+ZG+...+ZG (|X| copies of ZG).
local #pG,
der, row, r, i;
Table(G);
der:=[];
for r in RelatorsOfFpGroup(G) do
row:=[];
for i in [1..Length(FreeGeneratorsOfFpGroup(G))] do
Append(row, Der(G, r, i));
od;
Add(der,row);
od;
return GenerateAsZGModule(G,der);
end;
#***************************************************************
Is_ZLinearComb:=function(list, vector)
#***************************************************************
# Given a list of integer vectors of equal length
# and an integer vector of the same length, this
# function returns true if the vector is Z-linear
# combination of vectors in the list and false
# otherwise.
local B,
list_and_vector, reduced_list,
space, basis, coeff,
normal_list_and_vector, normal_list;
B:=false;
if list<>[]
then
list_and_vector:=StructuralCopy(list);
Add(list_and_vector,vector);
if RankMat(list_and_vector) = RankMat(list)
then normal_list_and_vector:=NormalFormIntMat(list_and_vector,2);
normal_list:=NormalFormIntMat(list,2);
if
normal_list_and_vector.normal{[1..normal_list_and_vector.rank]}=
normal_list.normal{[1..normal_list.rank]}
then B:=true;
fi;
fi;
fi;
return B;
end;
#***************************************************************
MinimalModuleGenerators:=function(G, S)
#***************************************************************
# Given a finitely presented finite group G=<X|R> and
# a set S = {v_1,...,v_n} of integer vectors of equal length
# k=|v_i| with k an integer multiply of |G|, the command
# T:=MinimalModuleGenerators(G,S)
# consracts a subset T of S as follows.
# The vector v_i are identified with elements in the free
# module ZG+...+ZG (k/|G| copies of ZG). Let A denote the
# abelian group consisting of all finite integer linear
# combinations of the elements in S. Let B denote the
# ZG-module generated by the elements of T. Then T is
# constructed to have the property A < B; moreover, no subset
# of T has this property.
local T,
temp, G_temp,
sublist_G_temp, except, index,
i, j;
temp:=[];
G_temp:=[];
for i in [1..Length(S)] do
if not (S[i] in G_temp)
then if not Is_ZLinearComb(G_temp,S[i])
then Add(temp, S[i]);
Append(G_temp, VectorPermutations(G,S[i]));
fi;
fi;
od;
T:=[];
except:=[];
for i in [1..Length(temp)] do
index:=[];
for j in [1..Length(temp)] do
if not(j in except) and i<>j
then Append(index, [Size(G)*(j-1)+1..Size(G)*j]);
fi;
od;
sublist_G_temp:=G_temp{index};
if Is_ZLinearComb(sublist_G_temp, temp[i])
then Add(except,i);
else Add(T, temp[i]);
fi;
od;
return T;
end;
#***************************************************************
IdentityModuleZBasis:=function(G)
#***************************************************************
# Given a finitely presented finite group G=<X|R>, the command
# S:=IdentityModuleZBasis(G);
# constract a set S of vectors that form a basis for the free
# abelian group underlying the module of identities \pi.
# Thus the vectors in S have length equal to |G|*|R|;
# the implicit ordering on the element of G is that given by
# the standart GAP command
# Elements(G);
# for the listing the elements of G.
local A, V, v,nf;
A:=FoxMatrix(G);
nf:=NormalFormIntMat(A,6);
V:=nf.rowtrans{[nf.rank+1..Length(A)]};
return LLLReducedBasis(V).basis;
#return BaseIntMat(V);
end;
#***************************************************************
IdentityModuleGenerators:=function(G)
#***************************************************************
# Given a finitely presented finite group G=<X|R>, the command
# T:=IdentityModuleGenerators(G)
# constracts a set T of integer vectors v_i of length
# |v_i|=|G|*|R|. The set T represents a minimal set of
# generators for the module of identities \pi.
local m;
m:= MinimalModuleGenerators(G, IdentityModuleZBasis(G));
return m;
end;
#***************************************************************
Resolution:=function(G,n)
#***************************************************************
# Given a finitely presented finite group G=<X|R>,
# and an integer number n>2, the command
# RES:=Resolution(G,n);
# construct a list RES such that for 2<i<n
# RES[i] is a minimal set of generators
# for the i-th term of a free ZG-resolution of Z.
local res, matrix,
nf, V,
mgen, i;
res:=[];
for i in [3..n] do
if i=3
then res[i]:=IdentityModuleGenerators(G);
else Table(G);
matrix:=[];
for mgen in res[i-1] do
Add(matrix, mgen);
od;
matrix:=GenerateAsZGModule(G,matrix);
nf:=NormalFormIntMat(matrix,6);
V:=nf.rowtrans{[nf.rank+1..Length(matrix)]};
V:=LLLReducedBasis(V).basis;
#V:=BaseIntMat(V);
res[i]:=MinimalModuleGenerators(G,V);
fi;
od;
return res;
end;
#####################################################################
########################END OF IRINA'S CODE##########################
IrinasRes:=Resolution(G,n);
FoxM:=FoxMatrix(G);
#####################################################################
Dimension:=function(n);
if n=0 then return 1; fi;
if n=1 then return Length(GeneratorsOfGroup(G)); fi;
if n= 2 then return Length(RelatorsOfFpGroup(G)); fi;
if n>2 then return Length(IrinasRes[n]); fi;
end;
#####################################################################
#####################################################################
ExtendIrinasRes:=function() #This function will add the first
local i, j, V; #two dimensions to Irinas Resolution.
IrinasRes[1]:=[];
IrinasRes[2]:=[];
for i in [1..Dimension(2)] do
V:=[];
for j in [1..Dimension(2)*OrderG] do
if j=(1+(i-1)*OrderG) then V[j]:=-1; else V[j]:=0; fi;
od;
Append(IrinasRes[2], [TransposedMat(FoxM)*V]);
od;
for i in [1..Dimension(1)] do
V:=[];
for j in [1..Dimension(1)*OrderG] do
if j=(1+(i-1)*OrderG) then V[j]:=-1;else
if j=Position(EltsG,GeneratorsOfGroup(G)[i])+(i-1)*Order(G) then
V[j]:=1;
else V[j]:=0;
fi; fi;
od;
V:=List([1..Order(G)],x->V[x+(i-1)*Order(G)]);
Append(IrinasRes[1],[V]);
od;
end;
#####################################################################
ExtendIrinasRes();
#####################################################################
Int2Pair:=function(i,m) #m=Order(G), i=Position in a vector
local j, x;
j:=i mod m;
x:=(i-j)/m;
if j=0 then return [x,m];
else
return [x+1,j];
fi;
end;
#####################################################################
#####################################################################
Boundary:=function(n,kk)
local B, i, j, p, w, k, StandardForm;
k:=AbsoluteValue(kk);
B:=IrinasRes[n][k];
StandardForm:=[];
for i in [1..Length(B)] do
if not B[i]=0 then
for j in [1..AbsoluteValue(B[i])] do
p:=Int2Pair(i,OrderG);
Append(StandardForm, [ [SignInt(B[i])*p[1],AbsoluteValue(p[2])] ]);
od;
fi;
od;
if kk>0 then return StandardForm;
else
return NegateWord(StandardForm);
fi;
end;
#####################################################################
return Objectify(HapResolution,
rec(
dimension:=Dimension,
boundary:=Boundary,
homotopy:=fail,
elts:=EltsG,
group:=G,
properties:=
[["type","resolution"],
["length",n],
["characteristic", Charact],
["reduced",true] ]));
end);
#####################################################################
#####################################################################
InstallGlobalFunction(ResolutionSmallGroup,
function(G,n)
local GG;
if IsFpGroup(G) then
return ResolutionSmallFpGroup(G,n);
fi;
GG:=Image(IsomorphismFpGroup(G));
GG:=SimplifiedFpGroup(GG);
return ResolutionSmallFpGroup(GG,n);
end);
#####################################################################