a Xi :ma h/0110314 1 [ma h.AT] 30 Oc 2001
Compu ing Cocycles on Simplicial Complexes∗
Roc´ıo Gonz´alez–D´ıaz, Ped o Real
Uni e sidad de Se illa, Dep o. de Ma em´a ica Aplicada I,
A da. Reina Me cedes, 41012 Se illa, Spain,
e-mails: ogo[email p o ec ed], [email protected]
Abs ac
In his no e, wo king in he con ex o simplicial se s [17], we gi e a de ailed
s udy o he complexi y o compu ing chain le el S een od squa es [20, 21], in
e ms o he numbe o ace ope a o s equi ed. This analysis is based on he
combina o ial o mula ion gi en in [5]. As an applica ion, we gi e he e an algo i hm
o compu ing cup–ip oduc s o e in ege s on a simplicial complex a chain le el.
1 In oduc ion
Cohomology ope a ions a e ools o calcula ing n-cocycles on he cohomology o spaces
(see, o example, [16, 19]). Un o una ely, up o he p esen , no symbolic compu a ional
sys em includes gene al me hods o inding ep esen a i e n–cocycles on he cohomol-
ogy o spaces, algeb as, g oups, e c. Recen ly, se e al me hods o inding 2–cocycles
ep esen ing 2–dimensional cohomology classes o ini e g oups ha e been designed (see
[4, 12, 14]). The me hod es ablished in [14] is based on he gene al heo y p esen ed in
[13] and i seems ha can be gene alized o highe dimension wi hou e o .
In his pape , we desc ibe a di e en p ocedu e based on a combina o ial o mula ion
gi en in [5] o an impo an class o chain le el cohomology ope a ions called S een od
squa es. The o mula we ob ain in [5] is essen ially an explici simplicial desc ip ion o
he o iginal o mula gi en by S een od [20] o he cup–ip oduc on simplicial complexes.
We no e ha a mod–2 explici o mula ion o he S een od cop oduc on he chain o a
simplicial se has also been gi en in (6.2) o Hess [11], using a di e en me hod.
∗Bo h au ho s a e pa ially suppo ed by he PAICYT esea ch p ojec FQM-0143 om Jun a de An-
daluc´ıa and he DGES-SEUID esea ch p ojec PB97-1025-C02-02 om Educa ion and Science Minis y
(Spain).
1
We wo k wi h simplicial se s [17] which a e combina o ial analogs o opological
spaces. Fi s , ou conce n he e is o s udy he “complexi y” (in e ms o numbe o
ace ope a o s in ol ed) o an algo i hm o compu ing (a chain le el) he in ege cup–
ip oduc s, using he o mula ion gi en in [5]. Finally, as an applica ion, we gi e an
algo i hm o compu ing chain le el S een od squa es on simplicial complexes.
We in eg a e he e ools o Combina o ics and Compu e Algeb a in a wo k o Alge-
b aic Topology, opening a doo o a compu a ional de elopmen in he sea ch o cocycles
in any deg ee (see [1] and [6]). A ea men o some o ou me hods has al eady been
p esen ed in [7].
In he li e a u e, he e is plen y o in o ma ion abou cup–ip oduc s and S een od
squa es (see [23] and [3] o a non–exhaus i e accoun o esul s). We hink ha he
algo i hmic echnique explained he e could be subs an ially e ined i i is sui ably com-
bined wi h ele an and well–known esul s on hese cohomology ope a ions and wi h
echniques o homological pe u ba ion o manipula ing explici homo opy equi alences
(see [2, 8, 9, 10]).
We a e g a e ul o P o . Julio Rubio o his help ul sugges ions o imp o ing he
algo i hms showed he e.
2 Topological and Algeb aic P elimina ies
The aim o his sec ion is o gi e some simplicial and algeb aic p elimina ies in o de o
pu in o con ex he p oblem o compu ing n–cocycles ( ia cup–ip oduc s and S een od
squa es). Mos o he ma e ial gi en in his sec ion can be ound in [15], [17] and [19].
Asimplicial se Xis a sequence o se s X0, X1,..., oge he wi h ace ope a o s
∂i:Xn→Xn−1and degene acy ope a o s si:Xn→Xn+1 (i= 0,1,...,n), which sa is y
he ollowing simplicial iden i ies:
(s1) ∂i∂j=∂j−1∂ii i < j ;
(s2) sisj=sj+1sii i≤j;
(s3) ∂isj=sj−1∂ii i < j ,
(s4) ∂isj=sj∂i−1i i > j + 1 ,
(s5) ∂jsj= 1X=∂j+1sj.
The elemen s o Xna e called n–simplices. A simplex xis degene a e i x=si(y) o
some simplex yand degene acy ope a o si; o he wise, xis non degene a e.
Le Rbe a ing which is commu a i e wi h uni . Gi en a simplicial se X, le us
deno e C∗(X) by he chain complex {Cn(X), dn}, in which Cn(X) is he ee R–module
2
gene a ed by Xnand dn:Cn(X)→Cn−1(X) is a R–module map o deg ee −1 called
di e en ial, de ined by dn=Pn
i=0(−1)i∂i.
Le s(C∗(X)) be he g aded R–module gene a ed by all he degene a e simplices o
X. In C∗(X), we ha e ha dn(s(Cn−1(X))) ⊂s(Cn−2(X)), hen
CN
∗(X) = {Cn(X)/s(Cn−1(X)), dn}is a chain complex called he no malized chain com-
plex associa ed o X.
Since dndn+1 = 0, we can de ine he homology o X,H∗(X), ha is he amily o
modules Hn(X) = Ke dn/Im dn+1.
Now, he cochain complex associa ed o CN
∗(X), deno ed by C∗(X;R), is he ee R–
module gene a ed by all he R–module maps om CN
∗(X) in o R, oge he wi h a map
called codi e en ial de ined by (δnc)(x) = c(dn+1(x)) i x∈CN
n+1(X) and c∈Cn(X;R).
We will say ha c∈Cn(X;R) is a n–cocycle i δ(c) = 0, and cis a n–cobounda y i he e
exis s ano he cochain c′∈C∗(X;R) such ha c=δ(c′).
In his way, we de ine he cohomology o Xwi h coe icien s in Rby
H∗(X) = Ke δn/Im δn−1. No ice ha a cocycle c ep esen s a class o cohomology.
3 Complexi y o Compu ing S een od Squa es
Fi s o all, le us show he explici o mula o he cup–np oduc ⌣non C∗(X;R) gi en
in [5]. The chain le el S een od squa es Sqi:Cj(X;Z2)→Cj+i(X;Z2) a e de ined om
his ope a ion in a e y easy way,
Sqi(c) = c ⌣nc, whe e n=j−i .
They sa is y ha i cis a j–cocycle, hen Sqi(c) is a (i+j)–cocycle.
Theo em 3.1 [5] Le Rbe he g ound ing and Xa simplicial se . Le c∈Cp(X;R),
c′∈Cq(X;R)and x∈CN
p+q−n(X); i nis e en, hen
c ⌣nc′(x) =
m
X
in=n
in−1
X
in−1=n−1
···
i1−1
X
i0=0
(−1)A(n)+B(n,m,¯
i)+C(n,¯
i)+D(n,m,¯
i)
c(∂i0+1 ···∂i1−1∂i2+1 · · · · ∂in−1−1∂in+1 ···∂mx)
•c′(∂0···∂i0−1∂i1+1 · · · · ∂in−2−1∂in−1+1 ···∂in−1x)
and i nis odd, hen
c ⌣nc′(x) =
m
X
in=n
in−1
X
in−1=n−1
···
i1−1
X
i0=0
(−1)A(n)+B(n,m,¯
i)+C(n,¯
i)+D(n,m,¯
i)
3
c(∂i0+1 ···∂i1−1∂i2+1 · · · · ∂in−2−1∂in−1+1 ···∂in−1x)
•c′(∂0···∂i0−1∂i1+1 · · · · ∂in−1−1∂in+1 ···∂mx)
whe e m=p+q−n, he symbol •is he p oduc in R,
A(n) = (1i n≡3,4,5,6mod 8,
0o he wise,
B(n, m,¯
i) =





















⌊n
2⌋
X
j=0
i2ji n≡1,2mod 4,
⌊n−1
2⌋
X
j=0
i2j+1 +nm i n≡0,3mod 4,
C(n,¯
i) =
⌊n
2⌋
X
j=1
(i2j+i2j−1)(i2j−1+···+i0)
and
D(n, m,¯
i) = ((m+in)(in+···+i0)i nis odd,
0i nis e en,
being ¯
i= (i0, i1,...,in).
As we can see, he gene al o ganiza ion o ace ope a o s in hese o mulae is simple
in he sense ha we dis inguish in some way n+1 ace ope a o s ∂i0, ∂i1,...,∂in; bu he
signs in ol ed ollow a complica ed o mula. Wo king o e Z2, his p oblem is elimina ed.
The aim o his sec ion is o gi e an idea o he complexi y o he algo i hm o
compu ing n–cocycles based on he p e ious o mula ion.
Fi s o all, le us begin by gi ing a di e en desc ip ion o he cup–n o mula. Le
us conside an alphabe wi h only wo le e s: 0 and 1. So, wo ds in his alphabe a e
sequences o le e s 0 and 1. We coun he le e s o a wo d om he le o he igh
and we will suppose ha he i s le e on he le is in ze o posi ion.
Le mand nbe wo nonnega i e in ege s such ha n≤m. And le i0, i1,...,in∈Z
so ha 0 ≤i0< i1···< in≤m, hen he no a ion (i0, i1...,in)m ep esen s he wo d
wi h m+ 1 le e s such ha he e a e ze os in he posi ions i0, i1,...,inand ones in he
es , ha is,
i0i1i2i3in
1···101· · ·101···1 0 1 ···1 0 ······ 0 1 ···1.
4
In he wo d abo e, by j–block (1 ≤j≤n) we mean he block o ones in ij−1+ 1 un il
ij−1 posi ions and ze o in ijposi ion. The 0–block has ones in 0 un il i0−1 posi ions
and ze o in i0posi ion; and he (n+ 1)–block has ones in in+ 1 un il mposi ions. Tha
is,
0–block 1–block 2–block n–block (n+1)–block
z}| {
i0
1···1 0 z }| {
i1
1···1 0 z }| {
i2
1···1 0 ······ z }| {
in
1···1 0 z}| {
1···1
E en ually, he (n+ 1)–block can be he emp y wo d.
Now, gi en a wo d (i0, i1,...,in)mwe can make a pai o wo ds deno ed by
((i0, i1,...,in)+
m,(i0, i1. . . , in)−
m), in he ollowing way. I nis e en, hen
– he i s wo d o he pai , deno ed by (i0, i1,...,in)+
m, can be ob ained om he
wo d (i0, i1,...,in)mp ese ing he j–blocks wi h jodd, ha is,
1–bl. 3–bl. 5–bl. (n−1)–bl. (n+1)–bl.
z}| {
1···1 0 z }| {
1···1 0 z }| {
1···1 0 ······ z}| {
1···1 0 z }| {
1···1;
– he second wo d o he pai , deno ed by (i0, i1,...,in)−
mcan be ob ained om he
wo d (i0, i1,...,in)mp ese ing he j–blocks wi h je en, ha is,
0–bl. 2–bl. 4–bl. (n−2)–bl. n–bl.
z}| {
1···1 0 z }| {
1···1 0 z }| {
1···1 0 ······ z}| {
1···1 0 z }| {
1···1 0 .
I nis odd, hen he p ocedu e is analogous.
Some examples a e:
– he wo d 1101101 ep esen ed by (2,5)6is associa ed wi h he pai o wo ds:
((2,5)+
6,(2,5)−
6) = (110,1101) ;
– he wo d 00110 ep esen ed by (0,1,4)4is associa ed wi h he pai o wo ds:
((0,1,4)+
4,(0,1,4)−
4) = (0,0110) .
I is easy o see ha we can eco e he o iginal wo d (i0, i1,...,in)m om he pai
((i0, i1,...,in)+
m,(i0, i1, . . . , in)−
m) sui ably combining he j–blocks o bo h wo ds.
Fo example, i we ha e he pai
(111101011,011100) ,
5

we i s coun he numbe o le e s (in his case, m= 14), we de e mine he j–blocks in
each wo d o he pai
0–bl. 1–bl. 2–bl.
z}| {
11110 z}|{
10 z}|{
11 ,
0–bl. 1–bl. 2–bl.
z}|{
0z}| {
1110 z}|{
0!
and inally, we econs uc he o iginal wo d al e na ing he blocks o bo h wo ds
0 11110 1110 10 0 11 = (0,5,9,11,12)14 .
Iden i ying he le e 1 in he posi ion kwi h ∂kand 0 wi h he iden i y, he gene al
o mula o he cup–np oduc admi s he ollowing ep esen a ion:
c ⌣nc′(x)
=
m
X
in=n
in−1
X
in−1=n−1
···
i1−1
X
i0=0
(−1)A(n)+B(n,m,¯
i)+C(n,¯
i)+D(n,m,¯
i)
c((i0, i1,...,in)+
mx)•c′((i0, i1,...,in)−
mx).
And he p oblem o coun ing he numbe o summands in he o mula o he cup–n
p oduc is equi alen o ha o inding all he possible ways o pu n+ 1 ze os in m+ 1
possible places, ha is,
m+ 1
n+ 1 !.
Bu , aking in o accoun ha cis a p–cochain and c′is a q–cochain, hen we only ha e
o conside he summands o he o mulae ha ing q−n ace ope a o s in he i s ac o
and p−nin he second one. Hence, in an analogous way ha in [5], a new combina o ial
de ini ion o cup–np oduc is gi en in he ollowing heo em.
Theo em 3.2 Le Rbe he g ound ing and Xa simplicial se . I c∈Cp(X;R),
c′∈Cq(X;R)and x∈CN
p+q−n(X), hen
c ⌣nc′(x)
=
m
X
in=S(n)
in−1
X
in−1=S(n−1)
···
i2−1
X
i1=S(1)
(−1)A(n)+B(n,m,¯
i)+C(n,¯
i)+D(n,m,¯
i)
c((i0, i1,...,in)+
mx)•c′((i0, i1,...,in)−
mx)
(1)
whe e m=p+q−n,•is he p oduc in R,
S(k) = ik+1 −ik−2+···+ (−1)k+n−1in+ (−1)k+nλ(n)−n
2+$k
2%
being λ(n) = pi ne en and λ(n) = qo he wise; and i0=S(0).
6
P oo .
Le us s a wi h c∈Cp(X;R) and c′∈Cq(X;R). I n < p o n < q hen c ⌣nc′is
ze o because he e is no any summand in he o mula wi h q−n ace ope a o s in he
i s ac o and p−n ace ope a o s in he second one. So, le us suppose ha n≤p
and n≤q.
I n= 0, hen p+q−i0=qand i0=p, so i0=p.
I n= 1, hen i1−1−i0=q−1 and p+q−1−i1+i0=p−1. So, i1−i0−q= 0 = q−i1+i0
and hence, i0=i1−qand i1≥q.
Le us suppose ha nis e en (i nis odd, he p oo is analogous), hen he numbe
o ace ope a o s in he i s ac o o he summands is
p+q−n−in+···+i2k+1 −1−i2k+···+i1−1−i0,(2)
and in he second one
in−1−in−1+···+i2k−1−i2k−1+···+i2−1−i1+i0.(3)
Since we only ha e o conside in he o mula o c ⌣nc′, he summands ha he numbe
o ace ope a o s in he i s ac o is q−nand p−nin he second one, ha is, (2) is
q−nand (3) is p−n, hen
p+q−n−in+···+i2k+1 −1−i2k+···+i1−1−i0−p+n
=in−1−in−1+···+i2k−1−i2k−1+···+i2−1−i1+i0−q+n
and hence,
i0=i1−i2+i3− · · · − in+p−n
2.(4)
Taking in o accoun in (4) ha i0≥0, we ge
i1≥i2−i3+···+in−p+n
2.
Using i0≤i1−1 in (4), we ha e
i2≥i3−i4+···+in−1−in+p−n
2+ 1 .
In gene al, le us suppose ha
ik≥ik+1 −ik+2 +···+ (−1)k+n−1in+ (−1)k+np−n
2+$k
2%,
o all 1 ≤k≤ℓ, and le us p o e ha his exp ession is ue in ℓ+ 1 wi h ℓodd (i ℓ
e en, he p oo is simila ). In he case k=ℓ−1, since iℓ−1≥iℓ−1, we ha e
iℓ−1≥iℓ−iℓ+1 +···+ (−1)ℓ+n−2in+ (−1)ℓ+n−1p−n
2+ℓ−1
2
7
and simpli ying, we conclude
iℓ+1 ≥iℓ+2 −iℓ+3 +···+ (−1)ℓ+nin+ (−1)ℓ+n+1 p−n
2+ℓ+ 1
2.
✷Now, le us s udy he numbe o summands in he o mula abo e. Gi en
ap–cochain c, a q–cochain c′and a nonnega i e in ege n, he p oblem o coun ing all
he summands in he o mula o c ⌣nc′is equi alen o ha o inding all he pai s o
wo ds ((i0, i1,...,in)+
m,(i0, i1,...,in)−
m) such ha he i s wo d has q−nle e s 1 and
he second wo d has p−nle e s 1. We ob ain he ollowing esul .
Theo em 3.3 Le Rbe he g ound ing. Le Xbe a simplicial se and na nonnega i e
in ege . I c∈Cp(X;R)and c′∈Cq(X;R), hen he numbe o summands aking pa
in he o mula (1) o c ⌣nc′is




q−jn+1
2k
jn
2k






p−jn
2k
jn+1
2k


.
P oo .
Fi s , le us suppose ha nis e en. Ou p oo s a s wi h he obse a ion ha he
i s ac o o a summand o he o mula (1) has q−n ace ope a o i and only i he
wo d (i0, i1,...,in)+
massocia ed o i has q−nle e s 1 and n
2le e s 0. Then he numbe
o wo ds (i0, i1,...,in)+
mha ing exac ly q−nle e s 1 is he numbe o all he possible
ways o pu n
2ze os in q−n+n
2places,
q−n
2
n
2!.
Analogously, he wo d (i0, i1,...,in)−
massocia ed o he second ac o has p−nle e s
1 and n
2+ 1 le e s 0. Then he numbe o wo ds (i0, i1,...,in)−
mha ing p−nle e s 1
is he numbe o all he possible ways o pu n
2ze os ( he las ze o can no be changed)
in p−n+n
2places, ha is, p−n
2
n
2!.
And he same easoning applied o he case nodd gi es us wi h he esul ha he e
a e q−n+1
2
n−1
2!
possible wo ds (i0, i1,...,in)+
mwi h q−nle e s 1, and
p−n−1
2
n+1
2!
8
Table 1: Numbe o summands
in he o mula o in he o mula o
Theo em 3.1 Theo em 3.2
c3⌣2c420 6
c6⌣5c628 12
c12 ⌣4c10 11,628 1,260
c25 ⌣5c30 18,009,460 621,621
c60 ⌣5c70 4,925,156,775 68,222,616
c6⌣5c700 162,699,437,009,655 970,224
c60 ⌣50 c60 225,368,761,961,739,396 33,701,394,635,724,816
c6⌣5c7000 163,331,343,055,757,216,550 97,902,024
wo ds (i0, i1,...,in)−
mwi h p−nle e s one.
✷Le us see wi h se e al examples, he imp o emen o he las o mulae o he
cup–np oduc gi en in Theo em 3.2 espec o he i s o mulae gi en in Theo em 3.1.
Le us no e cpi c∈Cp(X;R).
Taking in o accoun ha S een od squa es a e de ined using cup–np oduc s, he
ollowing co olla y holds.
Co olla y 3.4 Le Z2be he g ound ing. Le ibe a nonnega i e in ege and c∈
Cj(X;Z2), hen he numbe o summands aking pa in he o mula o Sqi(c)is



jm
2k
jn
2k





jm+1
2k
jn+1
2k


,
whe e m=i+jand n=j−i.
4 Simplicial Complexes
Now, le us s udy a pa icula simplicial se . A (combina o ial) simplicial complex [18, 22]
is a collec ion Po nonemp y ini e subse s o some e ex se Vsuch ha i τ⊂σ⊂V
and σ∈P, hen τ∈P. I he e ex se is o de ed, we call Pan o de ed simplicial
complex. To e e y such o de ed simplicial complex we associa e a simplicial se SS(P)
as ollows. The se SSn(P) consis s o all o de ed (n+ 1)– uples h 0, 1,..., nio
e ices (called n–simplices), possibly including epe i ion, such ha he unde lying se
9
[14] Lambe, L.: An algo i hm o calcula ing cocycles. P ep in o Depa men o Ma h.
and Cen e o Inno a i e Compu a ion (1997) Uni e si y o Wales
[15] Mac Lane, S.: Homology. Classics in Ma h. (1995) Sp inge -Ve lag. Rep in o he
1975 edi ion
[16] Massey, W.: Singula Homology Theo y. G adua e ex s in Ma h. 56 (1952)
Sp inge -Ve lag
[17] May, P.: Simplicial objec s in Algeb aic Topology. Van Nos and (1967) P ince on
[18] Munk es, J. R.: Elemen s o Algeb aic Topology. Addison-Wesley Publishing Com-
pany (1984)
[19] Spanie , E. H.: Algeb aic Topology. McG aw-Hill (1966). Rep in ed by Sp inge -
Ve lag (1981)
[20] S een od, N. E.: P oduc s o cocycles and ex ensions o mappings. Ann. o Ma h.
48 (1947) 290–320
[21] S een od, N. E.: Reduced powe s o cohomology classes. Ann. o Ma h. 56 (1952)
47–67
[22] Weibel, C. A.: An in oduc ion o Homological Algeb a. Camb idge s udies in ad-
anced Ma h. 38 (1994) Camb idge Uni e si y P ess
[23] Wood, R. M. W.: P oblems in he S een od algeb a. Bull. London Ma h. Soc. 30
(1998) 449–517
16