On the computability of the Steenrod squares

Ann. Univ. Ferrara - Sez. VII - Sc. Mat. Vol. XLII, 57-63 (1996) On the Computability of the Steenrod Squares. PEDRO REAL (*) SUNTO - In questo lavoro offriamo in modo esplicito le formule di una serie de morfismi che controUano la mancanza di commutativit~ del prodotto cup a livello di cocateni, supponendo di lavorare con insiemi sempliciali; queste formule si stabliliscono in termini di morfismi componenti di una contrazione di Eilenberg-Zilber data. Di conseguenza, nel caso in cui l'insieme sempliciale sia finito in ogni dimensione, otterremo un algoritmo di calcolo di quadrati di Steenrod. ABSTRACT - We give explicitely the formulas of a sequence of morphisms which measure the failure of commutativity of the cup product on the cochain level, provided that we work with simplicial sets; these formulas are established in terms of the component morphisms of a given Eilenberg-Zilber contraction. As a consequence, in the case in which the simplicial set is finite in each dimension, we obtain an algorithm for calculating Steenrod squares. 1. - Introduction. Recently, many authors have tried to reformulate several concepts from Algebraic Topology in an effective way, achieving methods to provide algorithms computing those concepts ([13], [14], [12], [9]). We are interested here in exhibiting an effective solution to the construction and computation of the Steenrod squares operations [16]. It is well-known that a classical procedure to define the Steenrod squares is based on the construction of a family of morphisms that measure the failure of commutativity of the cup product on the cochain level [2, sect. 6.2A]. (*) Indirizzo dell'autore: Univ. de Sevilla, Fac. de Inform~tica y Estadistica, Dpto. de Matem~tica Aplicada I, Avda. Reina Mercedes s/n, 41012 Sevilla (Spain); Fax: 34-54557878; e-maih [email protected] Math. Subject Classification (1991): 55S05. 58 PEDRO REAL From now on, following [1], this sequence of morphisms will be called higher diagonal approximation. In the literature, the existence of this higher diagonal approximation is always guaranteed by the acyclic models method [4]. In a semi-simplicial context [8], the technique of acyclic models can be considered as an actual algorithmic method (see [11]). In consequence, for each simplicial set X, we can determine a higher diagonal approximation in this way. In this paper, we develop another method to explicitely give the general formulas of a higher diagonal approximation, provided that we work with simplicial sets. Concretely, these formulas are established in terms of the component morphisms of a given Eilenberg-Zilber contraction. Therefore, in the case in which the simplicial set X is finite in each dimension, we obtain an algorithm for calculating cochains of X by the Steenrod squares. Finally we conclude that the problem of the computability of cochains by these cohomology operations exhibit in general an exponential complexity. In view of the plentiful literature existing about methods for defining Steenrod operations (see [6] for obtaining a non-exhaustive list), a remark seems us necessary. Our elementary presentation can be useful for a major understanding of the underlying structures which allow us to determine the homotopy type of spaces, as the same time as it can be a starting point for an algorithmic approach to cohomogical operations. 2. - Preliminaires. First, we will assume that we are working over a ground ring R which is commutative with unit. We will use the letters A, B .... to designate differential graduated modules over R or DG-modules, and the letters X, Y, ... to denote simplicial sets; the face and degenerancy operators of a simplicial set will be denoted by 3i and si, respectively. Finally, C. (X) and C* (X) will be the normalized chains and cochains of the simplicial set X respectively. Eilenberg and MacLane defined in [5] a contraction of a DG-module A onto a DG-module B as a triple (f, g, q~) in which f: A -, B (the projection of the contraction) and g: BoA (the injection of the contraction) are morphisms of DG-modules while ~b: A --*A is a morphism of graduated modules of degree 1 (raising dimensions by 1). It is required that (cl) fg = 1B; (C2) f~b = 0; (C3) ~bg = 0; (C4) ~d + d~ = gf - 1A ; (c5) ~ = o. ON THE COMPUTABILITY OF THE STEENROD SQUARES 59 An Eilenberg-Zilber contraction is a contraction of C,(X x Y) onto C,(X) | C,(Y), where X and Y are simplicial sets. There exists at least one: THEOREM 1 [3]. Let X and Y be simplicial sets. The Alexander-Whitney operator AW: C, (X x Y) --> C, (X) | C, (Y), the Eilenberg-MacLane operator EM: C, (X) | C, (Y) -~ C, (X x Y) and the Shih operator SHI: C,(X x Y) --~C.+i(Xx Y) of X and Y are defined by the following formulas: AW(xn x y~) = ~ ~ + 1"" ~n Xn @ ~0." ~i - lYn , i=0 EM(xp| = ~ (-1)sg(a,~)(S~q...s~lXp x s,p...s, lyq) , (a, t~) ~ {(P, q) - shuffles} SHI(x~ x y~) = n-p-q+sg(a, fl) = - ~(-1) (Sflq +n-p-q'" Sfll+n-p-qSn-p-q-I ~n-q+l"" ~nXn X X Sap +1 ~-Tt-P-q ~176 Sal ~-~-P-q ~-P-q'~ ~n-q-1 Y~), where the last sum is taken over all the indices 0 <<. q <<. n - 1, 0 ~< p <~ n - - q - 1, (a, fl) e {(p + 1, q) - shuffles} and sg(a, fl) = ~ (ai - (i - 1)). The triple (AW, EM, SHI) is a contraction of C,(Xx Y) onto C, (X) | C, (Y). The explicit formula for the Shih operator is given in [10]. 3. - The determination of a higher diagonal approximation. It is well-known that it is not possible to construct an Eilenberg-Zilber contraction with commutative projection (see, for example, [7, sect. 8.5]). We present in this section a new relation between the lack of commutativity of the Alexander-Whitney operator and the construction of a ~,higher coproduct,, which allows us to define the Steenrod squares. We will obtain this result, by proving the following theorem: THEOREM 3.2. Let A and B be two DG-modules. Let (fi g, ~) be a contraction of A onto B. Let h: A -~ A be an idempotent morphism of DG-modules. Let us suppose that the following relation holds (1) ~phg = O. 60 PEDRO REAL Then there exists a sequence of morphisms { fi }i ~ o , fi : A ~ B of degree i~ such that (2) fo=f, dBj~-(-1)ifidA=h'fi_l +(-1)ifi_lh if i~ l where h ' = fhg. Moreover, an explicit formula for the morphisms fi can be given (3) f~ =f(h~) ~ Vi >10. Now, we apply this theorem to the case in which the data are the Eilenberg-Zilber contraction (AW, EM, SHI) and the automorphism of transposition t,: C,(X xX)~C,(X x X) where t(x x y) = (y x x). From now on, we will denote the differentials of C, (X), C, (X x )X and C, (X)| C,(X) by d, d• and d| respectively. We easily can establish that SHIt, EM = 0; we obtain, thus, a sequence of morphisms {~}i~0 fii : C, (X x X) ~ C, (X) | C, (X) of degree i. with f~=(AW) (t,SHIP. verifying (4) d| - ( - 1)~j~ d • = Tj~ _ 1 + ( - 1)~j~ _ 1 t,, ifi~>l, where T: C, (X) | C, (X) ~ C, (X) @ C, (X) is defined by T(a| = (-1)Pqb| with a e Cp (X), b e Cq (X). Now, we can construct the higher diagonal approximation {Ai}i~0. where the morphism Ai: C,(X)----)C,(X)| is given by (5) A~ =A oA . and the morphism A: C,(X)-->C,(X x X) is defined by A(a)= a x a, Va ~ X. The morphism A 1 is a morphism of DG-modules (the AlexanderWhitney diagonal approximation) and the maps A i (i >>-2) satisfy relations: (6) d~Ai - (-1)iAid = TAi-1 + (-1)iAi1 9 It is well-known that a family of morphisms verifying (6) are used to construct the U-products and the Steenrod squaring operations (see, for ON THE COMPUTABII~ITY OF THE STEENROD SQUARES 61 example, [15, sect. 5.9]). Now, the definition of the cohomology operation Sqi: Hq(X) "-> Hq§ is: (7) {~ |215 sii<q, Sqi(c)(x) = si i > q, where c e Hom( Cq (X), Ze ) et x e Xq + i . Then, it is clear that, at least in the case in which X is finite in each dimension, this explicit formulation constitutes an actual algorithm. Moreover, this definition shows that the computation of cochains by Sq~ carries always the use of the Shih operator, which requires, in general, exponential time to give an answer. In fact, the sum that defines this operator is taken over the shuffles (special type of permutation). Roughly speaking, this morphism reflects in this case the passing from Geometry to Algebra. To sum up, computing Steenrod squares is a genuinely computationally difficult problem. We conjecture that the measure of the complexity of the computation of these cohomology operations is exponential. 4. - Proof of the Theorem 2. To prove the result, it suffices to verify the following condition: (8) ~dA hCphd~ = - ~h~hdA ~b . In fact, if the condition (8) is true, we can easily deduce the equality: (9) ~dA(h~ = (-l~-l(~bh~dA~, Vj >I 1, and this relation will allows us to show (2). Here, we firstly prove the equalities (2), supposing true the formulas (9); finally, we will establish the relation (8). For i = 1, we do not need the relation (9) to obtain (2)1. Using the property (c4) of a contraction, we have dBfh~ + fh~dA = ds]h~ + fh(gf1A - dAr = Since f and h are morphisms of DG-modules, = dsfh~ +fhgf-fh -fhdn~b =fhdAr + (fhg)f-fh -fhdAr = (fhg)f-fh 62 PEDRO REAL Now, we have to prove the relation (2)i, if i I> 2. First, we use the definition (3), dBfi -- (--1)ifidA = dBf(hd~) i + (-1) i+ lf(hdp)idA = = dBf(h~))i + ( _ 1)i + ifh(~h)i - 1 ~)dA = We make use of the property (c4) of a contraction, = dBf(hCp)i + ( _ 1)i + ifh(r - 1 (el__ 1A -- dA d~) = By (1) and (9), we have = dBf(h~)i + (_l)i + lfh(~h)i - igf+ (_l )i fh( r )i - 1 + (_l)ifh(~h)i - 1 dA r = = fhdA dfl( hdp )i - 1 + (_ l )i f( h~ )i - 1 h + fhd~dA ( hr ) i - 1 = = fh(dAd p + r + (_l)if(hgp)i-1 h = We consider now the properties (c3) and (c4) of a contraction, the idempotency of the DG-morphism h and the formulas (3); = fh(gf1A )(h~) i - ~ + ( - 1)i2~ _ i h = = (fag) f(hd~) i - 1 _ f~ h~(h~)~ - 2 + ( _ 1)ifi _ i h = = h'fi-1 + (-1)ij~-i h. This completes the proof of (2)i, i I> 1. Now we shall show that the relation (8) holds. First, using the property (c4) of the definition of contraction and the idempotency of the morphism h, we have h(gf - dA ~) -- ~dA ) h = 1A ; and, hence, we find hgfh - hdA ~h - h~dA h = 1A Composing this equality on the left and on the right with the homotopy operator q~, it turn out ~hgfh~ - ~hdA ~h~ - ~h~d.4 h~ = ~ ON THE COMPUTABILITY OF THE STEENROD SQUARES 63 Since h is a morphism of DG-modules and keeping in mind the relations (1) and (c5), we conclude ~)dA hCphdp = - ~bh~hdA r . REFERENCES [1] J. F. DAVIS, Higher Diagonal Approximations and Skeletons of K(z, 1)'s, Lect. Notes in Math., Springer-Verlag, 1126 (1983), pp. 51-61. [2] J. DIEUDONNI~, A History of Algebraic and Differential Topology, 1900-1960, Birkh~iuser, Basel, Boston (1989). [3] S. EILENBERG - J. A. ZILBER, On products of complexes, Am. J. Math., 75 (1959), pp. 200-204. [4] S. EILENBERG - S. MACLANE, Acyclic models, Am. J. Math., 67 (1953), pp. 282-312. [5] S. EILENBERG - S. MACLANE, On the groups H(z, n), I, Ann. Math., 58 (1953), pp. 55-106. [6] M. KAROUBI, Formes differentieUes non conmutatives et operations de Steenrod, Topology, 34, n. 3 (1995), pp. 699-715. [7] W. S. MASSEY, Singular Homology Theory, Springer-Verlag, New York (1980). [8] P. MAY, Simplicial Objects in Algebraic Topology, Van Nostrand, Princenton (1967). [9] P. REAL, Sur le calcul de groupes d'homotopie, C. R. Acad. Sci. Paris., 319, S6rie I (1994), pp. 475-478. [10] J. RUBIO, Homologie effective des espaces de lacets itdrds, Thesis at Grenoble University (October 25, 1991). [11] J. RuBIo - F. SERGERAERT, Supports acycliques et algorithmique, Ast@risque, 192 (1990), pp. 35-53. [12] J. RuBIo - F. SERGERAERT, A program computing the homology groups of loop spaces, SIGSAM Bulletin, 25 (1991), pp. 20-24. [13] R. SCHON, Effective Algebraic Topology, Memoirs of the Amer. Math. Soc., Vol. 451 (1991). [14] F. SERGERAERT, The computability problem in Algebraic Topology, Adv. Math., 104, 1 (1994), pp. 1-29. [15] E. H. SPANIER, Algebraic Topology, McGraw-Hill Book Comp., New York (1966). [16] N. E. STEENROD, Reduced powers of cohomology classes, Ann. Math., 56 (1952), pp. 47-67. Pervenuto in Redazione il 23 gennaio 1996. In forma definitiva il 21 ottobre 1996