# GAP V.3 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.3 functions for computing the module of # identities of a finite presentation of a finite group G, and for # computing the integral homology of G in dimensions n=1,2,3. # The file should be stored under the filename "homology.gap" and read # into GAP V.3 using the command Read("homology.gap"); . Further # instructions can then be obtained by typing the command Help(); . # ************************************************************************ # For all functions: # # *the list of records representing an element zg in # ZG+...+ZG (k copies of ZG)* # means the constraction that becomes clear if we consider # the following example. # Let G has a presentation . # So G = {1, x, y, xy}. # Let zg be an element in the free module ZG+ZG, e.g. # zg=(x+y+2xy)e1+(1+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:=[IdWord]), # rec(coeff:=3, word:=[y]) ] ] #******************************************** NullList:=k->List([1..k], x->0); #******************************************** #*************************************************************** 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 G.generators do d:=w*z^-1; if dG.generators[i] and w<>G.generators[i]^-1 then return rec(coeff:=0, word:=[]); else if w=G.generators[i] then return rec(coeff:=1, word:=[IdWord]); else return rec(coeff:=-1, word:=[w]); fi; fi; fi; l:=LastFactor(G,w); w:=w*l^-1; item:=rec(coeff:=apply(G,l,i,rem).coeff, word:=w*apply(G,l,i,rem).word); if item.word<>[] then Add(rem, item); fi; next:=apply(G,w,i,rem); return next; end; rem:=[]; d:=apply(G,w,i,rem); if d.word<>[] then Add(rem,d); fi; return 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; if not IsBound(G.elements) then Elements(G); fi; if not IsBound(G.size) then Size(G); fi; k:=Length(v)/G.size; zg:=[]; for i in [1..k] do zg[i]:=[]; l:=0; for j in [G.size*(i-1)+1..G.size*i] do l:=l+1; if v[j]<>0 then Add(zg[i], rec(coeff:=v[j], word:=[G.elements[l]])); fi; od; od; return zg; end; #*************************************************************** WordsToIntegers:=function(G,zg) #*************************************************************** # Given a finite group G and the list of records zg # representing an element in ZG+...+ZG (k copies), this # function returns the integer vector of length k*|G| # corresponding to this element. local list, position, l, d, i; if not IsBound(G.elements) then Elements(G); fi; if not IsBound(G.size) then Size(G); fi; list:=[]; for i in [1..Length(zg)] do l:=NullList(G.size); for d in zg[i] do position:=Position(G.elements,d.word[1]); l[position]:=l[position]+d.coeff; od; Append(list,l); od; return list; end; #*************************************************************** ProductZG:=function(pG,pg,pzg) #*************************************************************** # Given a permutation group pG, an element pg of this group # and a list of records pzg representing an element in # Z(pG)+...+Z(pG), this function returns the product # pg*pzg. local product, p, d, i; product:=[]; for i in [1..Length(pzg)] do p:=[]; for d in pzg[i] do Add(p, rec(coeff:=d.coeff, word:=[pg * d.word[1]] )); od; Add(product, p); od; return product; end; #*************************************************************** FoxMatrix:=function(G) #*************************************************************** # Given a finitely presented finite group G=, 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, pg, derivatives, matrices, matrix, product, der, n, g, r, d, i, j, i1, j1, i2, j2; if not IsBound(G.permGroup) then PermGroup(G); fi; pG:=G.permGroup; if not IsBound(pG.elements) then Elements(pG); fi; derivatives:=[]; for i in [1..Length(G.generators)] do derivatives[i]:=[]; for r in G.relators do der:=Der(G,r,i); for d in der do d.word[1]:=d.word[1]^pG.operationHomomorphism; od; Add(derivatives[i],der); od; od; matrices:=[]; for i in [1..Length(G.generators)] do matrices[i]:=[]; for j in [1..Length(G.relators)] do matrices[i][j]:=[]; for pg in pG.elements do product:=ProductZG(pG,pg,[derivatives[i][j]]); Add(matrices[i][j],WordsToIntegers(pG,product)); od; matrices[i][j]:=TransposedMat(matrices[i][j]); od; od; n:=G.size; matrix:=[]; for i in [1..n*Length(G.generators)] do matrix[i]:=[]; for j in [1..n*Length(G.relators)] do i1:=QuoInt(i,n); j1:=QuoInt(j,n); i2:=RemInt(i,n); if i2=0 then i2:=n; i1:=i1-1; fi; j2:=RemInt(j,n); if j2=0 then j2:=n; j1:=j1-1; fi; matrix[i][j]:=matrices[i1+1][j1+1][i2][j2]; od; od; G.foxMatrix:=matrix; return matrix; end; #*************************************************************** VectorPermutations:=function(G,v) #*************************************************************** # Given a finitely presented 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, z, p, d, U, u, pg; if not IsBound(G.permGroup) then PermGroup(G); fi; pG:=G.permGroup; if not IsBound(pG.elements) then Elements(pG); fi; U:=[]; z:=IntegersToWords(pG,v); for pg in pG.elements do p:=ProductZG(pG,pg,z); u:=WordsToIntegers(pG,p); Add(U,u); 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; #*************************************************************** 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; B:=false; if list<>[] then list_and_vector:=Copy(list); Add(list_and_vector,vector); if RankMat(list_and_vector) = RankMat(list) then reduced_list:=LLLReducedBasis(list).basis; space:=RowSpace(Rationals, reduced_list, "basis"); basis:=Basis(space); coeff:=Coefficients(basis,vector); if ForAll(coeff, IsInt) then B:=true; fi; fi; fi; return B; end; #*************************************************************** MinimalModuleGenerators:=function(G, S) #*************************************************************** # Given a finitely presented finite group G= 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, GenerateAsZGModule(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, [G.size*(j-1)+1..G.size*j]); fi; od; sublist_G_temp:=Sublist(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=, 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; if not IsBound(G.permGroup) then PermGroup(G); fi; if not IsBound(G.foxMatrix) then FoxMatrix(G); fi; A:=G.foxMatrix; v:=LLLReducedBasis(TransposedMat(A), "linearcomb").relations; V:=LLLReducedBasis(v).basis; G.identityModuleZBasis:=V; return V; end; #*************************************************************** IdentityModuleGenerators:=function(G) #*************************************************************** # Given a finitely presented finite group G=, 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; if IsBound(G.identityModuleGenerators) then return G.identityModuleGenerators; fi; if not IsBound(G.identityModuleZBasis) then IdentityModuleZBasis(G); fi; m:= MinimalModuleGenerators(G, G.identityModuleZBasis); G.identityModuleGenerators:=m; return m; end; #*************************************************************** PrintZG:=function(zg) #*************************************************************** # Given the list of records representing an element # in ZG+...+ZG, this function prints this element. local x, i, j; for i in [1..Length(zg)] do if zg[i]<>[] then Print("("); for j in [1..Length(zg[i])] do x:=zg[i][j]; if AbsInt(x.coeff)<>1 then if x.coeff>0 then Print("+",x.coeff,"*"); else Print(x.coeff,"*"); fi; else if x.coeff=-1 then Print("-"); else Print("+"); fi; fi; if x.word[1]=IdWord then Print("1"); else Print(x.word[1]); fi; od; Print(")e",i,"+"); fi; od; Print("\b"," "); Print("\n"); end; #*************************************************************** PrintZGlist:=function(G,S) #*************************************************************** # Given a finitely presented finite group G= # and a set S={v_1,...,v_n} of integer vectors of equal # length k=|v_i| with k an integer multiply of |G|, # this function prints the corresponding (in the usual way) # elements in the free module ZG+...+ZG (k/|G| copies of ZG). local zg; for zg in S do PrintZG(IntegersToWords(G,zg)); od; end; #*************************************************************** IntegralHomology:=function(G,n) #*************************************************************** # Given a finitely presented finite group G= and an # integer 1<=n<=3, the command # H:=IntegralHomology(G,n); # constructs the list H of abelian group invariants of the # finite homology group H_n(G,Z). local makeI, I, E, A, B, AT, Q, U, V, W, space, basis, coeff, rel, FF, H, z, q, v, w, r, i, j; makeI:=function(k,s) local I, i, j; I:=List([1..k], x->NullList(k*s)); for i in [1..k] do for j in [(i-1)*s+1..i*s] do I[i][j]:=1; od; od; return I; end; if not IsBound(G.size) then Size(G); fi; if n=1 then return AbelianInvariants(G); elif n=2 then if not IsBound(G.elements) then Elements(G); fi; I:=makeI(Length(G.generators), G.size); B:=[]; for z in G.generators do q:=NullList(G.size); q[1]:=-1; q[Position(G.elements, z)]:=1; Append(B, VectorPermutations(G, q)); od; E:=Copy(I); Append(E, TransposedMat(B)); if not IsBound(G.foxMatrix) then FoxMatrix(G); fi; A:=G.foxMatrix; AT:=TransposedMat(A); Q:=[]; for i in [1..Length(G.relators)] do Append(Q, List([1..G.size], x->AT[G.size*(i-1)+1])); od; W:=AT-Q; elif n=3 then I:=makeI(Length(G.relators), G.size); if not IsBound(G.identityModuleGenerators) then IdentityModuleGenerators(G); fi; A:=G.foxMatrix; V:=G.identityModuleGenerators; E:=Copy(I); Append(E,A); W:=[]; for v in V do w:=VectorPermutations(G,v)-List([1..G.size], x->v); Append(W,w); od; fi; U:=LLLReducedBasis(TransposedMat(E), "linearcomb").relations; W:=LLLReducedBasis(W).basis; space:=RowSpace(Rationals, U, "basis"); basis:=space.basis; coeff:=[]; for w in W do Add(coeff,Coefficients(basis,w)); od; FF:=FreeGroup(Length(U)); rel:=[]; for i in [1..Length(coeff)] do r:=IdWord; for j in [1..Length(coeff[1])] do if coeff[i][j]<>0 then r:=r*FF.generators[j]^coeff[i][j]; fi; od; Add(rel,r); od; H:=FF/rel; return AbelianInvariants(H); end; #************************ Help:=function() #************************ Print( "*************************************************************\n", "FoxMatrix(G)\n", "*************************************************************\n\n", "Given a finitely presented finite group G=, the command\n", " A:=FoxMat(G);\n", "constructs the integer matrix A representing the homomorphism\n", " delta: C2 --> C1,\n", "where C2 is the direct sum ZG+ZG+...+ZG (|R| copies of ZG),\n", " C1 is the direct sum ZG+ZG+...+ZG (|X| copies of ZG).\n\n", "*************************************************************\n", "IdentityModuleZBasis(G)\n", "*************************************************************\n\n", "Given a finitely presented finite group G=, the command \n", " S:=IdentityModuleZBasis(G);\n", "constract a set S of vectors that form a basis for the free\n", "abelian group underlying the module of identities \pi.\n", "Thus the vectors in S have length equal to |G|*|R|;\n", "the implicit ordering on the element of G is that given by\n", "the standart GAP command\n", " Elements(G);\n", "for the listing the elements of G.\n\n", "*************************************************************\n", "MinimalModuleGenerators(G,S)\n", "*************************************************************\n\n", "Given a finitely presented finite group G= and \n", "a set S = {v_1,...,v_n} of integer vectors of equal length\n", "k=|v_i| with k an integer multiply of |G|, the command\n", " T:=MinimalModuleGenerators(G,S)\n", "consracts a subset T of S as follows. \n", "The vector v_i are identified with elements in the free\n", "module ZG+...+ZG (k/|G| copies of ZG). Let A denote the abelian\n", "group consisting of all finite integer linear combinations \n", "of the elements in S. Let B denote the ZG-module generated by\n", "the elements of T. Then T is constructed to have the property \n", "A < B; moreover, no subset of T has this property.\n\n", "**************************************************************\n", "IdentityModuleGenerators(G)\n", "**************************************************************\n\n", "Given a finitely presented finite group G=, the command \n", " T:=IdentityModuleGenerators(G)\n", "constracts a set T of integer vectors v_i of length\n", "|v_i|=|G|*|R|. The set T represents a minimal set of generators\n", "for the module of identities \pi.\n\n", "**************************************************************\n", "PrintZGlist(G, S)\n", "**************************************************************\n\n", "Given a finitely presented finite group G=\n", "and a set S={v_1,...,v_n} of integer vectors of equal\n", "length k=|v_i| with k an integer multiply of |G|, \n", "this function prints the corresponding (in the usual way)\n", "elements in the free module ZG+...+ZG (k/|G| copies of ZG).\n\n", "**************************************************************\n", "IntegralHomology:=function(G,n)\n", "**************************************************************\n\n", " Given a finitely presented finite group G= and an\n", " integer 1<=n<=3, the command\n", " H:=IntegralHomology(G,n);\n", " constructs the list H of abelian group invariants of the\n", " finite homology group H_n(G,Z).\n\n" ); end; #************************ Test:=function() #************************ local F,x,y,G,B,A,sum,S,T,rels; Print("\n\nWe shall enter a presentation of the group G=A4 ...\n"); F:=FreeGroup("x","y"); x:=F.1; y:=F.2; rels:=[ x^3, y^2,(x*y)^3]; G:=F/rels; Print("The generators of G are ", G.generators, "\n"); Print("The relators of G are ", G.relators, "\n\n"); Print("We shall enumerate the group G ...\n"); Size(G); Print ("The order of the group G=A4 was computed to be ", G.size, ".\n", "This is ", G.size=12, ".\n\n"); B:=(G.size=12); Print("We shall construct the marix A representing the homomorphism \delta ...\n"); A:=FoxMatrix(G); sum:=Sum(Sum(A)); Print("The sum of the elements of A was computed to be ",sum, ".\nThis is ", sum=132, ".\n\n"); B:=(sum=132) and B; Print("We shall construct a set S of vectors that form a basis for the free abelian\n","group underlying the module of identities /\pi ...\n"); S:=IdentityModuleZBasis(G); Print("S was found to have ", Length(S), " elements.\n", "This is ", Length(S)=23 , ".\n\n"); B:=(Length(S)=23) and B; Print("We shall construct a set T of integer vectors that represent a minimal set of\n","generators for the module of identities /\pi ...\n"); T:=IdentityModuleGenerators(G); Print("T was found to have ", Length(T), " elements.\n", "This is ", Length(T)=3 , ".\n\n"); B:=(Length(T)=3) and B; if B then Print("\nNO ERRORS WERE DETECTED\n"); else Print("\nERRORS OCCURRED WHEN THIS TESTFILE WAS RUN\n"); fi; end;