A Mathematica Notebook for Computing the Homology of Iterated Products of Groups

AMathematica Notebook for Computing the Homology of Iterated Products of Groups V. ´ Alvarez, J.A. Armario, M.D. Frau, and P. Real Dpto. Matem´atica Aplicada I, Universidad de Sevilla, Avda. Reina Mercedes s/n 41012 Sevilla, Spain {valvarez, armario, mdfrau, real}@us.es Abstract. Let Gbe a group which admits the structure of an iterated product of central extensions and semidirect products of abelian groups Gi(both finite and infinite). We describe a Mathematica 4.0 notebook for computing the homology of G, in terms of some homological models for the factor groups Giand the products involved. Computational results provided by our program have allowed the simplification of some of the formulae involved in the calculation of Hn(G). Consequently the efficiency of the method has been improved as well. We include some executions and examples. 1 Introduction The calculation of the homology of a given group is in general a difficult task. From a theoretical point of view, spectral sequences and resolutions have been traditionally used to solve the question. But calculations could not be carried out in practice, due to the complexity of the processes involved in the computations. In the past decade, the interest in explicitly compute both the (co)homology and the correspondent representative (co)cycles of a group, has increased surprisingly, accordingly to their applications to very different fields, such as coding theory and cryptography. This situation has motivated that most of Computer Algebra Systems (CAS) are now concerned about the design of functions for achieving homological calculations. For instance, Gap (Group, algorithms, programming [9]) includes a homology package [7], which is concerned with the calculation of the homology of simplicial complexes and the Smith’s normal forms of (preferably sparse) integer matrices. Magma [18] includes a routine for computing the homology of p-groups [5]. The Kenzo system [6] provides an environment for achieving calculations in the framework of effective homology [21]. More recently, Ellis is developing a homological algebra library for use with the Gap computer algebra system (termed Hap [11], homological algebra programming), which intends to be a complete tool to make basic calculations in the cohomology of finite and infinite groups. All authors are partially supported by the PAICYT research project FQM–296 from Junta de Andaluc´ıa (Spain). A. Iglesias and N. Takayama (Eds.): ICMS 2006, LNCS 4151, pp. 47–57, 2006. c Springer-Verlag Berlin Heidelberg 2006 48 V. ´ Alvarez et al. Though the Kenzo system has incorporated some routines for the calculation of the homology of central extensions (in light of the work in [20]), as far as we know, none of these packages handles the class of groups that we are concerned with. We intend to cover this gap with the Mathematica notebook [1] which is presented here, for computing the homology of iterated products of central extensions and semidirect products of abelian groups. ThemainreasonforwhichwehavedecidedtoworkonMathematica instead of other CAS is that all the systems cited above work in terms of resolutions. We prefer to work in terms of “contractions”, that is, at the level of reduced complexes of resolutions, following the philosophy in [8,21]. In most cases, both ways turn out to be equivalent [4]. Our preferences come from the fact that we want to elude the recursiveformulaeprovidedbythecomparison theorem for resolutions. We prefer to work with explicit formulae from the first moment. For instance, the formulae in [19] for the maps involved in the Eilenberg-Zilber theorem, will allow us to perform explicit formulae for the maps describing a homological model for the iterated products that we are concerned with. Furthermore, our method may be extended to cover iterated products of other groups for which homological models are known, such as finitely generated torsion-free nilpotent groups [17,15], finite p-groups [16,10], finitely generated two-step nilpotent groups [12] and metacyclic groups [13]. We have programmed the formulae of [3] for constructing a homological model for a semidirect product of abelian groups, and the formulae implicitly described in [20] for constructing a homological model for a central extension of abelian groups. The term homological model refers to a contraction φ:¯ B(ZZ[G]) f   ghG from the reduced bar construction of the group G(i.e. the reduced complex associated to the standard bar resolution) to a differential graded module of finite type hG, so that H∗(G)=H∗(¯ B(ZZ[G])) = H∗(hG) and the homology of hG may be effectively computed by means of Veblen’s algorithm [22] (involving the Smith’s normal forms of the matrices representing the differential operator). Here φ:¯ B(ZZ[G]) f   ghG denotes a contraction, a special type of homotopy equivalence, where apart from the usual relations fg =1,1−gf =dφ +φd,the annihilation properties fφ =0,φg =0,φφ = 0 are satisfied. We must note that a routine in Mathematica which calculates the Smith’s normal form of a matrix over the integers was provided a decade ago by David Jabon [14]. Using this package and the formulae above, the notebook finally computes the homology of the input group. We organize the paper as follows. Section 2 is devoted to describe the formulae concerning the homological models for central extensions and semidirect AMathematica Notebook for Computing the Homology 49 products of abelian groups described in [20] and [3], respectively. The notebook itself is described in Section 3. In Section 4 we prove some results about simplifications on the formulae, which had been previously conjectured, attending to some output data provided by our program. Section 5 is devoted to show some executions and examples. 2 Describing Homological Models for the Factors Let Gbe an iterated product of central extensions and semidirect products of abelian groups Gi,1≤i≤n. In this section, we describe a homological model for Gin terms of some homological models for each of the factor groups Gi. 2.1 A Homological Model for ZZ Let E(u) denote the free DGA-algebra endowed with trivial differential and generators 1 (at degree 0) and u(at degree 1), so that u·u=0. The comparison theorem for resolutions provides a homological model for ZZ (see [4] for details), φZ:¯ B(ZZ[ZZ]) fZ   gZE(u), which is a subtle modification of that in [8] (they differ just in the homotopy operator φZ). Here gZ(u) = [1], fZ([n1|···|nq]) = n1u, if q=1 0,if q>1and φZ[n1|...|nk]=⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ (−1)k nk−1  i=1 [n1|...|nk−1|i|1],if nk>1 0,if nk=−1,0,1 (−1)k −nk−1  i=1 [n1|...|nk−1|−i|1],if nk<1 (1) 2.2 A Homological Model for ZZn Let Γ(v) denote the free DGA-algebra endowed with trivial differential and generators γk(v) (at degree 2k,k≥0, γ0(v) = 1), such that γk(v)γh(v)=(k+h)! k!h!γk+h(v) In [8] a homological model φZn:¯ B(ZZ[ZZn])fZn   gZn (E(u)⊗Γ(v),d)forZZnis also described, such that d(u)=0,d(u⊗v)=n·uand gZn(u) = [1], gZn(γk(v)) =  xi∈Zn [1|x1|···|1|xk],g Zn(uγk(v)) =  xi∈Zn [1|x1|···|1|xk|1] 50 V. ´ Alvarez et al. fZn[x1|y1|···|xm|ym]=[ m  i=1 δxi,yi]γm(v), fZn[x1|y1|···|xm|ym|z]=[z m  i=1 δxi,yi]uγm(v), for δxi,yi=0,x i+yi<n 1,x i+yi≥n and φZn([x1|···|xk]) = −ϕZn([x1|···|xk]), for ϕZn[]=0,ϕZn[x]= x−1  i=1 [1|i], ϕZn[x|y|σ]= x−1  i=1 [1|i|σ]+δx,y n−1  k=1 [1|k|ϕZnσ](2) 2.3 A Homological Model for a Central Extension Here A×αGdenotes the central extension of Aand Gby means of the 2-cocycle α:G×G→A, such that (a, g)(a,g)=(a+a+α(g,g),g+g). In case that αis a 2-coboundary, then A×αGis isomorphic to the direct product A×G. A homological model φAG:¯ B(ZZ[A×αG])fAG   gAG (hAG, dAG) for a central extension A×fG,forAbeinganabeliangroup,isdescribedin[20],intermsofhomological models φA:¯ B(ZZ[A]) fA   gA (hA, dA)andφG:¯ B(ZZ[G]) fG   gG (hG, dG) of the factor groups Aand G. Explicitly, fAG =(fA⊗fG)t∩AWδψϕ gAG =ϕψEMLδ(gA⊗gG)t∩ φAG =ϕ−1ψ−1(SHIδ+EMLδ(1 ⊗φG+φA⊗gGfG)t∩AWδ)ψϕ dAG =dA⊗1+1⊗dG+(fA⊗fG)t∩ i≥0 (−1)i[(1 ⊗φG+φA⊗gGfG)t∩]i(gA⊗gG) (fA⊗fG)t∩=(fA⊗fG)(1 −t∩ i≥0 (−1)i[(1 ⊗φG+φA⊗gGfG)t∩]i)(1 ⊗φG+φA⊗gGfG) (gA⊗gG)t∩= i≥0 (−1)i[(1 ⊗φG+φA⊗gGfG)t∩]i(gA⊗gG) (1 ⊗φG+φA⊗gGfG)t∩= i≥0 (−1)i[(1 ⊗φG+φA⊗gGfG)t∩]i(1 ⊗φG+φA⊗gGfG) t∩=AWδ  i≥0 (−1)i(SHIδ)iEML AWδ=AW(1 −δ i≥0 (−1)i(SHIδ)iSHI) EMLδ= i≥0 (−1)i(SHIδ)iEML SHIδ= i≥0 (−1)i(SHIδ)iSHI δ((an−1,...,a 0),(gn−1,...,g 0)) = −((an−2,...,a 0),(gn−2,...,g 0))+ (−α(gn−2,g n−1)+an−2,−α(gn−3,g n−2+gn−1)+α(gn−3,g n−2)+an−3,..., ...,−α(g0,g 1+...+gn−1)+α(g0,g 1+...+gn−2)+a0),(gn−2,...,g 0)) AMathematica Notebook for Computing the Homology 51 ϕ([(a0,g 0),...,(an,g n)]) = ((a0,g 0),...,(an,g n)),ifA×αGisabelian (−1)n 2+1((an,g n),...,(a0,g 0)),otherwise ψ[(an−1,g n−1),...,(a0,g 0)] = ([an−1,a n−2+α(gn−2,g n−1),...,a 0+α(g0,g 1+...g n−2+gn−1)],[gn−1,...,g 0]) ψ−1([an−1,...,a 0],[gn−1,...,g 0]) = [(an−1,g n−1),(an−2−α(gn−2,g n−1),g n−2),..., ...,(an−i−α(gn−i,g n−i+1 +...+gn−2+gn−1),g n−i), ...,(a0−α(g0,g 1+...+gn−2+gn−1),g 0)] AW((an−1,...,a 0),(gn−1,...,g 0)) = n  i=0 (an−1,...,a n−i)⊗(gn−i−1,...,g 0) EML((ap−1,...,a 0)⊗(gq−1,...g 0)) = (ap−1,...,a 0)(gq−1,...g 0) SHI((an−1,...,a 0),(gn−1,...,g 0)) = n−1  q=0 n−p−q  p=0 ((an−1,...,a p+q+1,0),(gn−1,...,g p+q+1,g p+q+...+gq))|| (ap+q,...,a q)(qq−1,...,g 0) The symbol refers to the shuffle product, so that the output of (ap−1,...,a 0)(gq−1,...,g 0) consists in the sum of all the different shuffles of the tuples, such that the inner order in the lists is preserved. The sign correspondent to a particular shuffle depends on the number of positions that elements aihave got ahead of elements gj. 2.4 A Homological Model for a Semidirect Product Here A×αGdenotes the semidirect product of Aand Gby means of the homomorphism α:G→Aut(A), such that (a, g)·(a,g)=(a+α(g)(a),g+g). In case that αis the zero map, then A×αGconsists in the direct product A×G. A homological model φAG:¯ B(ZZ[A×αG])fAG   gAG (hAG, dAG) for a semidirect product A×αG,forGbeinganabeliangroup,isdescribedin[3],intermsofhomological models φA:¯ B(ZZ[A]) fA   gA (hA, dA)andφG:¯ B(ZZ[G])fG   gG (hG, dG)ofthefactor groups Aand G. The formulae for central extensions given before also apply for a semidirect product, with the following exceptions, δ((an−1,...,a 0),(gn−1,...,g 0)) = −((an−2,...,a 0),(gn−2,...,g 0))+ +((α(gn−1)(an−2),...,α(gn−1)(a0)),(gn−2,...,g 0)) ψ[(an−1,g n−1),...,(a0,g 0)] = ((α(g−1 n−1)(an−1),...,α(g−1 n−1+...+g−1 0)(a0)),(gn−1,...,g 0)) ψ−1((an−1,...,a 0),(gn−1,...,g 0)) = ((α(gn−1)(an−1),g n−1),...,(α(g0+...g n−1)(a0),g 0)) 52 V. ´ Alvarez et al. 2.5 A Homological Model for an Iterated Product Let Gbe an iterated product of central extensions and semidirect products of abelian groups, which admits the form A× αG,forAand Galso being possibly iterated products. Here A× αGdenotes a single central extension or a single semidirec product, as it is the case. This way, a homological model for Ghas been already described in the subsections above, provided some homological models for Aand Gare known. In fact, we do know these homological models for Aand G. It suffices to iterate this scheme, until we arrive to homological models for ZZ or ZZn. 3TheNotebook 3.1 Codifying the Group An iterated product Gof central extensions and semidirect products of abelian groups Gi,1≤i≤n, is codified as a rooted binary tree, such that every inner vertex represents a product, their sons being the correspondent factor groups. As usual, a inner vertex contributes two sons in the level immediately below. This way, the number of leaf vertices coincides with the number of factor groups Gi. In order to obtain the group G, the inner vertices (i.e. single products) of the tree must be chosen from bottom to the top level (root vertex), from left to the right while staying at the same level. For instance, the binary tree of Figure 1 represents an iterated product. G3 G4 G1 2 3 1 G2 Fig. 1. A binary tree representing the product (G1×(G2×G3)) ×G4 We use a list for representing this binary tree, which we term tree-list.In fact, Mathematica is one of the most appropriate systems for handling with lists. Proceeding level by level, from top to the bottom, from left to the right, every vertex (but those placed on the last level) will be codified as an integer, attending to the correspondences in the table below. AMathematica Notebook for Computing the Homology 53 Label Meaning 0 leaf vertex 1direct product 2semidirect product A×αG 3semidirect product Gα×A 4centralextension A×αG 5centralextension Gα×A Example 1. Consider the dihedral group D4t=ZZ2t×αZZ2,forα:ZZ2→Aut(ZZ2t) such that α(0)(x)=xand α(1)(x)=−x. The list codifying this group consists in {{2}}. There is no need to add the list {0,0}corresponding to the last level. Example 2. Consider the central extension ZZ2t×αZZ2,forα:ZZ2×ZZ2→ZZ2t being the 2-cocycle α(gi,g j)=t 2+1ifgi=gj=1 0otherwise The list codifying this group consists in {{4}}. Once again, we do not take into account the list {0,0}corresponding to the last level. Example 3. Consider the iterated product (ZZt×α2ZZ2)×α1ZZ2,forα2being the 2-cocycle α2:ZZ2×ZZ2→ZZtdefined as α2(gi,g j)=t 2+1ifgi=gj=1 0otherwise and α1being the dihedral action α1(a, b)=−bif a=1 bif a=0 The list codifying this group consists in {{2},{4,0}}. 3.2 Codifying the Homological Models The homological models described in the precedent section involve several structures, such as: –Linear combinations. –Products of exterior and divided power algebras. –Elements in a cartesian simplicial product X×Y, linear combinations of tuples ((x1,y 1),...,(xn,y n)). –Elements in a tensor product X⊗Y, linear combinations of tuples (x1,...,x p) ⊗(y1,...,y q). –Formal series. 54 V. ´ Alvarez et al. We now describe the way in which these structures are codified. –The elimination of the attribute Listable on the addition and product functions provided by Mathematica supplies at once the possibility of making linear combinations with lists. –Each of the groups Gi=ZZnigivesrisetoaproductPi=E(ui)⊗Γ(wi), whereas each group Gj=ZZ gives rise to a single Pj=E(uj). The elements in hG = n  i=1 Piare codified as linear combinations of tuples of length n,such that if mis the jth entry of a tuple, it refers to the generator um(mod 2) ⊗ γm 2(w) (notice that only 0 and 1 entries are permitted in case of Pj=E(uj) factors coming from Gj=ZZ). These tuples are ordered as numbers of n digits. For instance, if G=ZZ2×ZZ×ZZ2,abasisforhG on degree 3 is given by {(0,0,3),(0,1,2),(1,0,2),(1,1,1),(2,0,1),(2,1,0),(3,0,0)}. –Tuples are codified as lists, in a natural way. –Formal series, which are always finite when applied on a concrete element, are codified in terms of the command NestList. 3.3 Calculating the Homology As Veblen’s algorithm indicates [22], in order to compute the homology Hi(G)it is necessary to calculate the Smith’s normal forms of the matrices Miand Mi+1 representing the differential operators diand di+1. Our program firstly computes the matrices Miand Mi+1. Afterwards, we use the SmithNormalForm.na package [14] and finally compute Hi(G). Though the actual version of the notebook does not provide representative i-cycles, it could be straightforwardly adapted to this end. In fact, such an option was available in an earlier (not published) version of the notebook, which ran only over finite groups. 3.4 Input and Output Data In these circumstances, we may now determine exactly what the input and output data are. Input Data: –The correspondent tree-list for the group G. –The cardinalities of each elementary factor group ZZ or ZZn. The notation is 0forZZ and n>1forZZn.Noticethatkfactor groups correspond to k−1 products, and vice versa. –The maps αiinvolved in the ith product, Ji× αi Ki. The user should attend to the tree-list for the group G, in order to identify the index icorresponding to each product, as well as the syntax to use for codifying the elements in Jiand Ki, since they could be in turn iterated groups themselves. –Finally, the desired degree k, in order to compute Hk. AMathematica Notebook for Computing the Homology 55 Output data: –The homology Hk(G). As soon as the computation has finished, the user is asked for going on computing Hk+1, since half of the computations (those corresponding to dk+1)may be reused. 4 Simplifications on the Formulae Calculations achieved with our program have provided some evidences of annihilation properties on some summands on the maps characterizing the homological models of the precedent sections. We include here the results that we have finally proved. Proposition 1. In the case of a homological model for a semidirect product, the morphism SHIδreduces to SHI,aswellasEMLδreduces to EML,andAWδ reduces to AW −AW δSHI. Proposition 2. In the case of a homological model for a semidirect product, the morphism t∩reduces to t∩([am−1,...,a 0]⊗[gn−1,...,g 0]) = (−1)m([α(gn−1)(am−1),...,α(gn−1)(a0)] −[am−1,...,a 0]) ⊗[gn−2,...,g 0] 5 Executions and Examples We compute here the matrices M2and M3corresponding to d2and d3,aswellas the homology groups H1and H2of some finite groups. These and other examples have provided essential information in order to calculate the total number of cocyclic Hadamard matrices on the correspondent groups, some of which seems to be new [2]. Example 4. Consider the family of groups ZZ2t×αZZ2,fort∈IN a nd αbeing the 2-cocycle f(1,1) = t 2+1. t1 2 3 4 5 M2⎛ ⎝20 00 02⎞ ⎠⎛ ⎝22 00 04⎞ ⎠⎛ ⎝23 00 06⎞ ⎠⎛ ⎝25 00 08⎞ ⎠⎛ ⎝26 00 010⎞ ⎠ M3⎛ ⎜ ⎜ ⎝ 000 0−20 020 000 ⎞ ⎟ ⎟ ⎠⎛ ⎜ ⎜ ⎝ 020 0−20 040 000 ⎞ ⎟ ⎟ ⎠⎛ ⎜ ⎜ ⎝ 030 0−20 060 000 ⎞ ⎟ ⎟ ⎠⎛ ⎜ ⎜ ⎝ 050 0−20 080 000 ⎞ ⎟ ⎟ ⎠⎛ ⎜ ⎜ ⎝ 060 0−20 0100 000 ⎞ ⎟ ⎟ ⎠ H1ZZ2⊕ZZ2ZZ2⊕ZZ4ZZ12 ZZ16 ZZ2⊕ZZ10 H2ZZ2ZZ20 0 ZZ2