A∞-persistence

blank line UNIVERSIDAD DE MÁLAGA FACULTAD DE CIENCIAS Programa de Doctorado en Matemáticas PhD thesis (Tesis doctoral) A∞-persistence Candidate (Doctorando): Francisco Belchí Guillamón Advisor (Director): Aniceto Murillo Mas Málaga, 2015 AUTOR: Francisco Belchí Guillamón http://orcid.org/0000-0001-5863-3343 EDITA: Publicaciones y Divulgación Científica. Universidad de Málaga Esta obra está bajo una licencia de Creative Commons Reconocimiento-NoComercialSinObraDerivada 4.0 Internacional: Cualquier parte de esta obra se puede reproducir sin autorización pero con el reconocimiento y atribución de los autores. No se puede hacer uso comercial de la obra y no se puede alterar, transformar o hacer obras derivadas. http://creativecommons.org/licenses/by-nc-nd/4.0/legalcode Esta Tesis Doctoral está depositada en el Repositorio Institucional de la Universidad de Málaga (RIUMA): riuma.uma.es 2 g Esta tesis ha sido parcialmente financiada por una beca para la Formaci´on de Personal Investigador (FPI) del antiguo Ministerio de Ciencia e Innovaci´on, el Proyecto de Investigaci´on MTM2010-18089 del Ministerio de Econom´ıa y Competitividad, el Grupo de Investigaci´on Consolidado FQM213 de la Junta de Andaluc´ıa y la red ACAT de la European Science Foundation. Aniceto Murillo Departamento de Álgebra, Geometría y Topología Universidad de Málaga AP. 59, 29080 Málaga, SPAIN Por la presente, como Director y Tutor de la tesis doctoral de D. Francisco Belchí Guillamón que lleva por título "A∞-persistence", AUTORIZO la presentación de la misma para que pueda ser defendida como Tesis Doctoral según la legislación vigente. Asimismo, INFORMO que el mencionado trabajo es totalmente original y que ha dado lugar a la siguiente publicación que lo avala: Francisco Belchí, Aniceto Murillo, "A∞-persistence", Applicable Algebra in Engineering, Communication and Computing: Volume 26, Issue 1 (2015), 121139. ISSN 0938-1279. doi: 10.1007/s00200-014-0241-4. Hago constar por último que ningún contenido ni resultado de la anterior publicación ha sido utilizado en ninguna otra tesis ni trabajo de investigación. Y para que así conste y surta los efectos oportunos, firmo el presente escrito en Málaga a 10 de Octubre de 2015 Aniceto Murillo Mas En record de la Carme Guàrdia. Sempre forta. Sempre positiva. (In memory of Carme Guàrdia. Always strong. Always positive.) Quiero dar las gracias a la gente que ha marcado más significativamente los años que he dedicado a esta tesis. A mi familia, y en especial a mis padres, por haberme transmitido amor por encima de todas las cosas. A mi familia de acogida en Málaga: Lali, Carlos y Juan Carlos, por acogerme tan cálidamente (con y sin terral) durante los últimos tres años. A Oihana, por lo personal y lo matemático. A nuestro Luis. A Marco, David y los demás compis del a veces superpoblado despacho. A PePe, por alegrarme el día tantas y tantas veces hablando de nuestras matemáticas. Ojalá podamos repetirlo (de manera formal o no) un número 𝐿∞ de veces. A Diek; de mayor quiero tener lo que tú tienes con Espe (¡pero no con Espe!). A mis alfajores Nahuel y Nacho. Por muchos tumbos que dé, cuando estemos juntos siempre me sentiré en casa. A Mònica, Jorge y mi gente de Barcelona. A mi director de tesis, Aniceto Murillo, porque sólo con él habría podido hacer una tesis y porque unas palabras suyas en persona siempre han bastado para motivarme, desbloquearme o darme un punto de vista nuevo. Gracias por tu paciencia y comprensión, y por haberme engañado para acabar cogiéndole el gustillo a la homotopía racional. ;-) A todo el maravilloso grupo de personas en el departamento: Nieves (que confió en mí desde el principio, dándome la oportunidad de compartir docencia con ella), Viru (el gran sabio con un pasado oscuro), Luisa (siempre haciéndonos la vida más fácil) y todos los demás. Un gracias muy especial a Antonio Díaz, por seguir haciendo de mí un guerrero y por tantos comentarios útiles sobre mi tesis. A los profesores de la Universitat de Barcelona que me formaron. En especial a Paco Guillén y a Carles Casacuberta. Si no me hubiera encontrado con ellos en el pasado, difícilmente habría acabado haciendo esta tesis. I would like to express my sincere gratitude to Robert Ghrist and Graham Ellis for being so welcoming during my visit to their respective institutions. I would also like to thank Jim Stasheff for his suggestions on my first paper, Paweł Dłotko for mentioning Zigzag Persistence to me when I didn't know about it, Vladimir Dotsenko and Tornike Kadeishvili for pointing out to me what I was getting wrong about 𝐴∞-structures, and Nick Scoville for his valuable feedback on this dissertation. And of course, thanks to that spilt cup of milk. Introduction 15 for which ∆m6= 0 and ∆0 m06= 0. Then, the numbers k:= min{n|∆n6= 0}and min{n|∆0 n6= 0} coincide, (H∗(X),{0, . . . , 0,∆k,0, . . .})and (H∗(X),{0, . . . , 0,∆0 k,0, . . .}) are isomorphic A∞-coalgebras and the numbers dim Ker ∆k|Hp(X)and dim Ker ∆0 k|Hp(X) coincide too, for all p≥0. In the same direction, we prove: Proposition 3.2.12. Let Ldenote the Borromean rings. Then, any good A∞-algebra {mn}non H∗(S3−L)will satisfy m3|H1⊗H1⊗H16≡ 0, where H1denotes H1(S3−L). Note that we can obtain similar results for mn|Hp1(X)⊗...⊗Hpn(X) for arbitrary values of n, p1, . . . , pn. In this sense we also prove Proposition 3.2.13. To state it, let n=p+q+r,x= (x1, . . . , xp), y = (y1, . . . , yq),and z= (z1, . . . , zr). Consider three spaces S1, S2, S3in Rn(homeomorphic to three spheres) determined by the equations x= 0,kyk2+kzk2 4= 1 ((q+r−1)-dimensional sphere S1); y= 0,kzk2+kxk2 4= 1 ((p+r−1)-dimensional sphere S2); z= 0,kxk2+kyk2 4= 1 ((p+q−1)-dimensional sphere S3); 16 Introduction Notice that the case p=q=r= 1 yields Borromean rings. In some sense more general than in the case of knots, these spaces Siare not pairwise linked, which makes the obvious Massey product being defined, and moreover, denoting by Kthe disjoint union of S1, S2and S3, we prove the following: Proposici´on 3.2.13. With the notation above, any good A∞-algebra {mk}k on H∗(Sn−K)will have m3|Hp⊗Hq⊗Hr6≡ 0, where Hkdenotes Hk(Sn−K). All these results support our interest in studying the persistence of the mentioned numbers along a filtration, which we explain next in terms of A∞-coalgebras and homology, although it also works for A∞-algebras and cohomology. Let K:K0//K1//. . . //KN be a sequence of topological spaces and continuous maps. In most applications, on works with filtrations, i.e., Kwill consist of nested simplicial/cubical/CW subcomplexes and inclusions K0//K1//. . .//KN. For every p≥0 and 0 ≤i≤j≤N, assume that the dimension of the pth homology group of Kiis finite, dim Hp(Ki)<∞, and let fi,j p:Hp(Ki)−→ Hp(Kj) and fi,j :H∗(Ki)−→ H∗(Kj) denote the maps induced in homology by the composition Ki//Ki+1 //. . . //Kj. Introduction 17 Classical persistence describes, for each p≥0, the evolution of the pth Betti number βp(X) = dim Hp(X) along Kby studying the so called persistent groups Hi,j p(K) := Im fi,j p,0≤i≤j≤N. Specifically, it defines a multiset of intervals (i.e., a set in which every element is an interval and has an assigned multiplicity), called the pth barcode, that satisfies the following: Theorem 1.2.4. [23, §3] (Fundamental Theorem of Persistent Homology) For every p≥0, the pth barcode of Kis well-defined and, for all 0≤i≤j≤N, the dimension of the persistent group Hi,j p(K)equals the number of intervals in the pth barcode of K(counted with multiplicities) which contain the interval [i, j]. In particular, dim Hp(Ki)equals the number of intervals in the pth barcode of K(counted with multiplicities) which contain i. We give a new proof of this classical result in §1.2 (see the proofs of Lemma 1.2.7 and Theorem 1.2.4). This result guarantees easy computations (as discussed in §3.3) and allows a visual picture that captures the information of all the persistent groups at once. Moreover, results on stability [28] tell us that in a certain sense, the number of long intervals in the pth barcode is robust with respect to noise and to small variations in the input and that this number encloses significant features of the original data. Inspired by this, we do the following. Choose a good A∞-coalgebra structure {∆i n}non the homology of each term Ki, that we shall use along the rest of the introduction. For each p≥0 and for each n≥1, we want to describe the evolution of the number dim Ker ∆n|Hp(X)along K. For that purpose, we define what we call ∆n-persistent groups (∆n)i,j p(K) = Im fi,j p|∩j k=iKer(∆k n◦fi,k p),0≤i≤j≤N, and a multiset of intervals, that we call the pth ∆n-barcode, that satisfy the following: 18 Introduction Corollary 3.6.5. For every p≥0and n≥1, the pth ∆n-barcode of Kis well-defined and, for all 0≤i≤j≤N, the dimension of the ∆n-persistent group (∆n)i,j p(K)equals the number of intervals in the pth ∆n-barcode of K (counted with multiplicities) which contain the interval [i, j]. In particular, dim Ker ∆i n|Hp(Ki)equals the number of intervals in the pth ∆n-barcode of K(counted with multiplicities) which contain i. This is one of the most important results in the dissertation. Here is the path we followed to prove it. First notice that if we choose a random basis of LN i=0 Hp(Ki), computing the numbers dim Hi,j p(K) by studying the evolution of the elements in that basis along Kwould be costly inasmuch as it would involve checking if the images by fi,j pof linearly independent homology classes become linearly dependent. Theorem 1.2.4 can be restated in terms of the existence of a basis which allows a much simpler computation: Theorem 1.2.8. [23, §3] For every p≥0, there exists a basis Bof LN i=0 Hp(Ki) such that, for all 0≤i≤j≤N, the dimension of the persistent group Hi,j p(K)can be computed by counting the number of p-homology classes of the basis that do not vanish in the corresponding range: dim Hi,j p(K) = #{β∈ B ∩Hp(Ki)|fi,jβ6= 0}. In A∞-persistence, choosing a random basis of LN i=0 Hp(Ki) and computing the numbers dim(∆n)i,j p(K) by studying the evolution of the elements in that basis along Kwould be even more costly, since it would involve checking further subtleties (see §3.3 for details). In this direction, we start by proving: Theorem 3.3.5. Fix some integers p≥0and n≥1. If fi,i+1 p(Ker ∆i n)⊆ Ker ∆i+1 nfor all 0≤i < N, then there exists a basis Bof LN i=0 Hp(Ki)such that, for every 0≤i≤j≤N, the dimension of the ∆n-persistent group (∆n)i,j p(K)can be computed by counting the number of p-homology classes of the basis that do not ∆n-fall asleep in the corresponding range: dim(∆n)i,j p(K) = #{β∈ B ∩Hp(Ki)|fi,kβ∈Ker ∆k n−{0}for all k=i, . . . , j}. Introduction 19 Furthermore, this number equals #{β∈ B ∩Hp(Ki)|fi,jβ∈Ker ∆j− {0}}. See Def. 3.3.1 for the meaning of ∆n-falling asleep and §3.5 for the explanation of the chosen terminology. It is worth pointing out that there are cases in which we can indeed apply Theorem 3.3.5: Theorem 3.4.1. With coefficients over the rationals Q, let K0be a 1connected CW complex and let Nbe an integer. If for all 0< i ≤N,Ki denotes a 1-connected space obtained attaching to Ki−1a cell such that dim M p≥0 Hp(Ki) = dim M p≥0 Hp(Ki−1) + 1 (and hence every attachment produces new homology), then there exists a good A∞-coalgebra e H∗(Ki),{∆i n}nfor each 0≤i≤Nsuch that fi,i+1 Ker ∆i n⊆Ker ∆i+1 n, for every n≥1and 0≤i < N. If we go further ahead and see what happens if we do not restrict to the assumptions in Theorem 3.3.5, we find a potential intermittent behaviour of the homology classes along Kthat we describe in §3.5. In essence, Theorem 3.5.1 shows how homology classes can, through the glasses of A∞-persistence, appear and disappear several times along K. Finally, thanks to Zigzag Persistence [20], we demonstrate that we can still get a result in the style of Theorem 3.3.5 without the assumptions therein. For every 0 ≤i≤N, fix an arbitrary good A∞-coalgebra structure {∆i n}n on H∗(Ki). Here is the statement. Theorem 3.6.1. For every p≥0and n≥1, there exists a basis Bof LN i=0 Hp(Ki)such that, for all 0≤i≤j≤N, the dimension of the ∆npersistent group (∆n)i,j p(K)can be computed by counting the number of phomology classes of the basis that do not ∆n-fall asleep in the corresponding 20 Introduction range: dim(∆n)i,j p(K)=#{β∈ B ∩Hp(Ki)|fi,kβ∈Ker ∆k n−{0}for all k=i, . . . , j}. Rearranging the information in the last result allows us to define the pth ∆n-barcode mentioned before (see §3.6 for details) and to conclude the appealing Corollary 3.6.5 stated above. On the computational side, we do not implement any algorithms or conduct a performance analysis. Rather, on the one hand, we enhance an attractive algorithm by P. Real et al. [80] that enables us to compute good A∞-coalgebra structures on the homology of CW complexes through the use of discrete vector fields (see Algorithm 2.3.5). On the other hand, we set up an abstract algorithm to compute the pth ∆n-barcodes of A∞-persistence in the most general case (see Algorithm 3.7.1). This thesis is organized as follows. In Chapter 1 we recall the necessary concepts on Persistence and give a new proof for one of its most important theorems. First of all, we display in §1.1 how the initial sequences Kare usually built in two very common applications – the study of point-cloud datasets and digital images. Secondly, in §1.2, we explain the basics of Persistent Homology and give an alternative proof of the Fundamental Theorem of Persistent Homology (see proofs of Lemma 1.2.7 and Theorem 1.2.4). Thirdly, we recall in §1.2 the Zigzag Decomposition heorem and algorithm we will need in Chapter 3. Chapter 2 consist of the background on A∞-(co)algebras plus some contributions of ours on how to compute them and on realizing how powerful they are. In §2.1 we set notation and recall the notion of a particular case of A∞- (co)algebras that is crucial for our approach – differential graded (co)algebras. Next, we explore A∞-(co)algebras: first, from the theoretical side in §2.2, as deformations of differential graded (co)algebras, and then computationally in §2.3, explaining our modification to an algorithm by P. Real et al. Finally, in §2.4 we show the power of A∞-(co)algebras through some results, classical and new. Introduction 21 It is in Chapter 3 where we develop the core of our theory. In its introduction, we describe scenarios (that will be extended in §3.2.2 and §3.2.3) in which it is natural to consider the use of A∞-persistence. We present in §3.1 the numbers (like dim Ker ∆i n|Hp(X)) we want to study, given a good A∞- coalgebra structure on the homology of a space X(or a good A∞-algebra structure on its cohomology). If we take two different such structures on H∗(X) (or on H∗(X)), their corresponding numbers can differ in general (§3.2.1), but we point out situations in which these numbers must necessarily be equal and situations in which they do not need to be equal but nevertheless provide information on the homotopy type of X(§3.2.2 and §3.2.3). These numbers will play the role that Betti numbers play in Persistent Homology in the sense that we will define a version of them for sequences of topological spaces and continuous maps (§3.3) K0//K1//. . . //KN and we will prove decomposition results that makes it easier to compute such “persistent numbers” and to visualize them all at once. Specifically, we first make some assumptions in order to prove one such result in §3.3 and present in §3.4 a construction that can be used under somewhat strong conditions to guarantee that we can apply such first decomposition result. If we get rid of all constraints, a curious intermittent behaviour (that justifies the awakeasleep terminology) can take place (§3.5) and we need a different approach to prove the most general decomposition theorem (§3.6). Finally, we make some remarks on how to compute A∞-persistence in the most general case (§3.7). In addition, as some of our results and examples lie heavily in classical facts from rational homotopy theory, we include for completeness an Appendix containing an overview of this theory and the results we use. Chapter 1 Persistent Homology Persistent Homology sprang independently from three different sources around the nineties. These three pillars consist of the Size Theory created by the group of M. Ferri and P. Frosini at the University of Bologna, the doctoral work of V. Robins at the University of Colorado Boulder, and the biogeometry project of H. Edelsbrunner at Duke University. These different sources led to two significantly different approaches to describe the shape of a space, so we should clarify which one this thesis follows. On the one hand, Size Theory [8,16,32,47] emphasizes that the meaning of the term “shape” depends on the context. If we want to study specific shape attributes of some objects, we must first think of continuous real-valued functions that take into account only the shape properties that are relevant to our problem, while disregarding the irrelevant ones. Then, we do the following with each of these functions: using a construction that involves 0dimensional homology, the function induces a signature for each of the spaces to be studied – this is a simpler object associated to a space so that congruent shapes have the same signature. Some of these signatures are built by means of functions encoding distance from center of mass or from an axis, curvature or torsion, speed or greyscale colour tone, when applicable. Size theory has been used in this fashion to identify writers from their handwriting [44], letters from monograms [43] and also sign language gestures [53,62,100]; to 23 24 Chapter 1. Persistent Homology classify leukocytes [45] and hepatic lesions [2]; to evaluate risk and intensity of cyclones [6] and more [9,46,76,77]. On the other hand, the approach to Persistent Homology by V. Robins, H. Edelsbrunner et al. focuses only on shape properties that are preserved by homotopy equivalences. More specifically, they try to compute the homology groups (of all degrees, not only degree 0 as above) of spaces, usually unknown ones, described for instance by means of finite point samples. This approach has had notable applications in many areas such as digital imaging [89], sensor networks [33], molecular modelling [3], dynamical systems [38,88] and speech pattern analysis [15]. In this dissertation we follow this second approach. We do not restrict to only (co)homology groups, but we study further structure on (co)homology as well. The idea would be to try to construct signatures for point-cloud datasets, induced by higher order operations in (co)homology. We devote this chapter to present the necessary background on the theory of Persistence we use. Here are some classical references of the first steps in Persistent Homology [23,39,103], and some of the many surveys on the topic available in the literature [18,37,50,102]. Consider an unknown closed subset Xof a metric space and a known finite subset Pof X. We would like to estimate topological properties of the space Xout of the point sample P. For instance, Pmay come from some statistical data and we may want to know about the space Xmodelling the data. Specifically, we are interested in the Betti numbers of the underlying space, {βp(X)}p≥0. The problem when trying to estimate them through a finite point sample is that these invariants are not at all robust to discontinuous changes in the input space. Persistent homology tackles this issue by constructing invariants which are robust in this sense but still have the kind of discriminatory power of Betti numbers. Here we present an outline of this chapter as we roughly explain how Persistent Homology works. Out of the point cloud P(or another input such as a digital image, for 1.2. Persistent Homology 31 have marked with arrows 14 non-trivial 1-cycles of Sx∈P ¯ B(x, 2/2) whose homology classes are born at this step and generate H1Sx∈P ¯ B(x, 2/2) (see Figure 1.2b). For = 3, all connected components have merged in a single one, and H1ˇ C3(P)∼ =k⊕k, where one of these copies of the field of coefficients kis generated by the 1-cycle marked with an arrow and the other is generated by the big 1-cycle (see Figure 1.2c). Notice that the homology class of the small 1-cycle is born at this step, and not in the previous one ε= 2, because this class is not the image of a homology class of Sx∈P ¯ B(x, 2/2), since all 1-dimensional homology classes of Sx∈P ¯ B(x, 2/2) die entering Sx∈P ¯ B(x, 3/2). For values of εbetween 4 and 67, both inlcuded, the simplicial complex ˇ C(P) consists of one connected component and has β1ˇ Cε(P)= 1, this Betti number being non-zero thanks to the central 1cycle (see Figures 1.2d, 1.2e, 1.2f, 1.2g). For ε≥68, ˇ C(P) is contractible (see Figure 1.2h). In particular, there are both a 0-dimensional homology class and a 1-dimensional homology class that are alive for a wide range of values of ε. Definition 1.2.3. For every 0 ≤i≤j≤Nand p≥0 we define the pth persistent homology group of the sequence Kbetween Kiand Kjas the vector space Hi,j p(K):= Im fi,j p and its corresponding persistent Betti number as βi,j p(K):= dim Hi,j p(K). We will usually omit the reference to the sequence Kand simply write Hi,j p and βi,j p. For each homology degree p≥0, we build a multiset of intervals to encode this information. Such a multiset is called the pth barcode and is defined as follows: 32 Chapter 1. Persistent Homology (a) = 1 (b) = 2 (c) = 3 (d) = 4 (e) = 5 (f) = 44 (g) = 65 (h) = 68 Figure 1.2: Given a point sample Pof an annulus, we show some terms of a filtration consisting of topological spaces Sx∈P ¯ B(x, ε/2) for a growing parameter . Figures 1.2a and 1.2b are scaled a little bigger to see them in more detail. 1.2. Persistent Homology 33 If at each stage we can attach an arbitrary finite number of cells, then two linearly independent classes can be born at the same time and merge some time later on, so we must have a way to choose which one survives and represents the merged class. To do so, it is enough to order the cells attached at each stage. In this general case, the pth barcode consists of intervals of the form [i, j) for 0 ≤i<j≤N, with multiplicity µi,j p:= βi,j−1 p−βi−1,j−1 p−βi,j p+βi−1,j p and intervals of the form [i, ∞) with multiplicity µi,∞ p:= βi,N p−βi−1,N p. Theorem 1.2.4 proves that the construction of this multiset is well defined, i.e., each µi,j pand µi,∞ pis greater or equal than zero. In Figure 1.3 we show an example of a barcode. 1 2 3 68  Figure 1.3: Here we show a representation of the 1st barcode (the one associated to the evolution of the first Betti number, β1) of the filtration in Example 1.2.2, where by each bar that starts at iand ends at jwe mean an interval of the form [i, j) in the barcode. There is another graphical representation used to encode this information – that of persistent diagrams [39]. They give the exact same information as barcodes, so we will just speak in terms of the latter. Next we proceed to give our own proof of the Fundamental Theorem of Persistent Homology, that we choose to restate as follows: 34 Chapter 1. Persistent Homology Theorem 1.2.4. [23, §3] (Fundamental Theorem of Persistent Homology) For every p≥0, the pth barcode of Kis well defined and for all 0≤i≤j≤N, the dimension of the persistent group Hi,j p(K)equals the number of intervals in the pth barcode of K(counted with multiplicities) which contain the interval [i, j]. In particular, dim Hp(Ki)equals the number of intervals in the pth barcode of K(counted with multiplicities) which contain i. We use Figure 1.4 to illustrate Theorem 1.2.4. 0N i j Figure 1.4: If this represents the pth barcode of K, Theorem 1.2.4 asserts that dim Hi,j p(K) = 4, since there are four intervals containing [i, j]. This result was first proved by Carlsson and Zomorodian in [23, §3] with a slightly different notation and vocabulary. They use the structure theorem for finitely generated modules over PIDs to show that this barcode construction is well-defined, and once this is done, it is straightforward to check that it implies the result. We will prove the same thing using Frobenius inequality on matrix ranks instead of the aforementioned structure theorem. Proposition 1.2.5. (Frobenius inequality on matrix ranks) Let A, B and Cbe matrices such that the products AB, ABC and BC are defined. Then rank(AB) + rank(BC)≤rank(B) + rank(ABC). 1.2. Persistent Homology 35 First we prove a lemma that will have Theorem 1.2.4 as a corollary. Definition 1.2.6. Apersistence module is a sequence of finite dimensional vector spaces and linear maps between them of the form V0//V1//. . . //VN. Lemma 1.2.7. Let V0 f0,1 //V1 f1,2 //. . . fN−1,N //VN be a persistence module and set fi,j :=    fj−1,j ◦. . . ◦fi,i+1, i + 1 < j, idVi, i =j. Then there always exists a multiset Mof intervals of the form [i, j)for 0≤ i < j ≤N, and of the form [i, ∞)for 0≤i≤Nsuch that for all 0≤ i≤j≤N, the dimension dim Imfi,j can be computed as the sum of the multiplicity of each interval in Mthat contains [i, j]. Proof. Let {di,j}i≤jbe a family of integers such that di,j = 0 for all i, j that do not satisfy 0 ≤i≤j≤N. For all 0 ≤i≤j≤N, define Ni,j := di,j −di−1,j −di,j+1 +di−1,j+1. If Ni,j ≥0 for every 0 ≤i≤j≤N, then we can define a multiset Mof intervals consisting of Ni,j−1intervals of the form [i, j), for all 0 ≤i < j ≤N, and Ni,N intervals of the form [i, ∞). Notice that for every 0 ≤i≤j≤N, the sum of the multiplicity of each interval in Mthat contain [i, j] equals Pk≤iPj≤lNk,l,which is precisely X k≤iX j≤ldk,l −dk−1,l −dk,l+1 +dk−1,l+1=X k≤idi,j −di−1,j=di,j. This shows a constructive way of building, out of a family of integers {di,j}i≤j, a multiset Mof intervals of the wanted form such that, for all 0≤i≤j≤N, dim Imfi,j = #{intervals in M that contain [i, j]}, as long as two conditions hold: 36 Chapter 1. Persistent Homology (a) di,j = 0 for all i, j that do not satisfy 0 ≤i≤j≤N. (b) Ni,j =di,j −di−1,j −di,j+1 +di−1,j+1 ≥0,for all 0 ≤i≤j≤N. Finally, if we define di,j :=    dim Imfi,j,0≤i≤j≤N, 0,otherwise, then condition (a) holds by construction and condition (b) reduces to Frobenius inequality on matrix ranks, finishing the proof. As a corollary, we prove Theorem 1.2.4. Proof. Apply Lemma 1.2.7 to the pth homology of the sequence K, Hp(K0)f0,1 p//Hp(K1)f1,2 p//. . .fN−1,N p//Hp(KN). Since the multiset construction from the proof of Lemma 1.2.7 applied to this persistence module coincides with the pth barcode defined above, we obtain the result. Notice that Hi,j pdescribes the p-dimensional homology classes that are born at or before Kiand die later than Kj,i.e., the classes that are alive from Kito Kj. If we take a random basis Bof LN i=0 Hp(Ki), the persistent Betti numbers can then be therefore expressed as βi,j p= #{β∈ B ∩Hp(Ki)|βis alive at Kkfor k=i, . . . , j}, but checking whether a class is alive at some point involves checking if it has merged with an older class, which is costly. A restatement of Theorem 1.2.4 guarantees there is always a good basis for which no checking mergings is needed: Theorem 1.2.8. [23, §3] For every p≥0, there exists a basis Bof LN i=0 Hp(Ki) such that, for all 0≤i≤j≤N, the dimension of the persistent group 1.3. Zigzag persistence 37 Hi,j p(K)can be computed by counting the number of p-homology classes of the basis that do not vanish in the corresponding range: dim Hi,j p(K) = #{β∈ B ∩Hp(Ki)|fi,jβ6= 0}. Let Xbe a closed subset of a metric space and Pa finite set of points in X. How do the barcodes of Pchange if we perturb it a little by either adding some noise points or by choosing a different point sample of X? Also, how do the barcodes of say a digital image of a lung change if we perturb it a little by either adding some noise points or by using a different method (maybe a different machine) to get another image of the same lung? Stability [28] rigurously proves that if these perturbations are small, then for every p≥0, the number of long intervals remain the same [28, Main Thm.]. Hence, these invariant quantities are the significant information in a barcode. Furthermore, stability also guarantees that if Pis a good enough point sample of X, we can compute the Betti numbers βp(X) out of the persistent homology of P[28, Homology Inference Thm.]. Chazal and Lieutier [26] independently obtained a similar result without the use of stability and [32, 82] proved more restrictive versions of this result. Example 1.2.9. Consider the filtration in Example 1.2.2, created from a point sample Pof an annulus. There are exactly one long interval in its 0th barcode and one long interval in its 1st barcode (see Figure 1.3), which agrees with the fact that the 0th and 1st Betti numbers of an annulus are β0=β1= 1. 1.3 Zigzag persistence We devote Chapter 3 to describing our own new tool – persistence of A∞- structures. A crucial tool to prove one of the main results in Chapter 3 (Theorem 3.6.1) is zigzag persistence, so we introduce this variant of persistence next. 38 Chapter 1. Persistent Homology In some situations, there is a persistence-flavoured kind of information we would like to obtain but we do not have a persistence module U1−→ U2−→ . . . −→ Ur, but rather just a sequence of the form U1←→ U2←→ . . . ←→ Ur, in which each ←→ can be either a forward map −→ or a backward map ←− (see Section 3.6 for an example of this). Zigzag persistence, introduced by Carlsson and de Silva in [20], describes some barcodes one can still get out of a structure like this. We now recall the basics of zigzag persistence [20]. A zigzag module U is a sequence of finite dimensional k-vector spaces U1 p1 ←→ U2 p2 ←→ · · · pr−1 ←→ Ur in which each pican be either a forward map fi −→ or a backward map gi ←−. Hence, persistence modules can be seen as zigzag modules where all maps are oriented in the same direction. A submodule X⊂Uof Uis a zigzag module X1←→ X2←→ . . . ←→ Xr where each Xi⊂Uiis a subspace, either fi(Xi)⊂Xi+1 or gi(Xi+1)⊂Xi, and the maps are the restrictions of those of U. A submodule X⊂Uis a direct summand, or simply, a summand of U, if there exists another submodule Y⊂Usuch that Ui=Xi⊕Yi, for all i. We write U=X⊕Y. It is important to remark that submodules are not, in general, summands. For instance [20, Ex. 2.1], in the zigzag module k1 −→ k, 1.3. Zigzag persistence 39 the map 0−→ k constitutes a submodule but not a summand. Given integers 1 ≤a≤b≤r, an interval of the form I[a, b]denotes a zigzag module I1 p1 ←→ I2 p2 ←→ · · · pr−1 ←→ Ir, in which, Ii=   k, a ≤i≤b, 0,otherwise, and pi=   1k, a ≤i≤b−1, 0,otherwise. Then, the main result in zigzag persistence states: Theorem 1.3.1. [48], [20, Theorem 2.5] (Zigzag’s Interval Decomposition Theorem) Every zigzag module Uis isomorphic to a direct sum of intervals, U∼ =⊕jI[aj, bj]. Gabriel’s paper [48] (in German) is the original statement of the theorem with a different vocabulary, [34] contains a friendlier form, and in [20, §4.1] the reader can find an extended and constructive version of this statement which can be used to develop explicit algorithms for the computation of the involved intervals. This result tells us we can encode all the information in a zigzag module U1←→ U2←→ . . . ←→ Ur by means of a multiset of integer intervals of the form [a, b]∩ {1, . . . , r}, 1≤a≤b≤r, that we write as [a, b] for simplicity. This multiset is called a zigzag barcode. 40 Chapter 1. Persistent Homology A notion of zigzag persistent diagram similar to that of the classical persistem diagrams can be constructed too, carrying the same information of the zigzag barcode. Remark 1.3.2. Notice the difference in notation between ordinary barcodes and zigzag barcodes of a persistent module. An interval [a, b + 1) in the classical barcode is written as [a, b] in the zigzag barcode, and one of the form [a, ∞) in the classical becomes [a, r]. On the one hand, the notation [a, b) for classical barcodes is particularly natural if we think of the indexing parameter as continuous – the interval [a, b) will correspond to a class that is alive at b−1 and not at b, but we do not know where it exactly died. On the other hand, the closed intervals are a good notation for zigzag barcodes because they allow us to keep symmetry between forward and backward maps. Zigzag decompositions present an extra hazard non-existent in ordinary persistence. We will deal with that in Section 3.6. 1.3.1 Algorithmic approach When explaining how to compute A∞-persistence (§3.7), we will use an algorithm by Carlsson and de Silva [20] to compute the barcode decomposition of zigzag modules, so we include here such an algorithm. Theorem 1.3.1 claimed that every zigzag module Uis isomorphic to a direct sum of intervals U∼ =⊕jI[aj, bj]. We now rephrase Algorithm 4.4 in [20] to compute such a decomposition out of an arbitrary zigzag module. The input is a zigzag module V:V1 p1 ←→ V2 p2 ←→ · · · pn−1 ←→ Vn in which each Vk pk ←→ Vk+1 can be either a forward map Vk fk −→ Vk+1 or a backward map Vk gk ←− Vk+1. The output consists of two collections of numbers {bk i}1≤i≤k≤nand {ck i}1≤i≤k≤n, whose meaning we will explain below. 2.1. Differential graded (co)algebras 47 Zp:= Ker ∂pand Bp:= Im ∂p+1. Therefore we can define the quotient Hp(M):= Zp Bp , which is called the the pth homology module of (M, ∂). Similarly, if (M, ∂) is a cochain complex . . . ∂p−2 //Mp−1∂p−1 //Mp∂p //Mp+1 ∂p+1 //. . . define Zp:= Ker ∂pand Bp:= Im ∂p−1 and call the quotient Hp(M):= Zp Bp the pth cohomology module of (M, ∂). Definition 2.1.9. Given dg modules (M, ∂),(N, ∂0) and an integer k, a differential graded map (or simply dg map) of degree kfrom Mto N f: (M, ∂)−→ (N, ∂0) consists of a family of linear maps {fp:Mp−→ Np+k}p∈N such that the following diagram communtes up to the sign (−1)k, . . . Mp−1 ∂ oo fp−1  Mp ∂ oo fp  Mp+1 ∂ oo fp+1  . . . ∂ oo . . . Np−1+k ∂0 ooNp+k ∂0 ooNp+1+k ∂0 oo. . . ∂0 oo i.e., ∂0◦f= (−1)kf◦∂. Amorphism of dg modules (or dg morphism) is a degree 0 dg map. 48 Chapter 2. A∞-structures Composition of dg maps is defined degreewise. Every dg map f:M−→ Ninduces a maps in (co)homology Hp(M)−→ Hp(N) or Hp(M)−→ Hp(N) (whichever appropriate), for all p∈N. Definition 2.1.10. Let (M, d) f ** g 44(N, d) be dg morphisms. A dg homotopy from fto gis a dg map φ:M−→ N of degree |φ|=−|d|such that f−g=dφ +φd. If there is a dg homotopy from fto g, we say that fand gare dg homotopic and write f≃g, or f≃ φg if we want to specify the dg homotopy φ. A dg morphism f:M−→ N is called a dg homotopy equivalence if there is a dg morphism g:N−→ M 2.1. Differential graded (co)algebras 49 such that gf ≃1Mand fg ≃1N. In that case, we say the the dg modules Mand Nare (dg homotopy) equivalent. Definition 2.1.11. Let (M, ∂) and (N, ∂0) be dg modules. Their tensor product (M⊗N, δ)is the dg module consisting of (M⊗N)p=M q+r=p Mq⊗Nr for all p∈N, with differential δ: (M⊗N)p−→ (M⊗N)p−1 defined by δ(a⊗b) = ∂a ⊗b+ (−1)qa⊗∂0b on elementes a∈Mq, b ∈Nr. The tensor product of dg maps is defined as for graded maps. Definition 2.1.12. Agraded algebra (A, µ)is a graded module Aequipped with a morphism of graded modules µ:A⊗A−→ A (called multiplication or product) that is associative, i.e., such that the following diagram commutes A⊗A⊗Aµ⊗1// 1⊗µ  A⊗A µ  A⊗Aµ//A Notation 2.1.13. From now on, we will use ab to denote µ(a⊗b) for any multiplication µ(associative or not). Thus, the morphism condition on the multiplication µof a graded algebra can be expressed by saying that if a∈Ap, b ∈Aq, then ab ∈Ap+q. 50 Chapter 2. A∞-structures Definition 2.1.14. Given graded algebras (A, µ) and (A0, µ0), a morphism of graded algebras from Ato A0 f: (A, µ)−→ (A0, µ0) is a graded morphism that is multiplicative, i.e., such that the following diagram commutes. A⊗Af⊗f// µ  A0⊗A0 µ0  Af//A0 Definition 2.1.15. Adifferential graded algebra (DGA) is a triple (A, ∂, µ)in which (i) (A, ∂) is a dg module, (ii) (A, µ) is a graded algebra, and (iii) µ:A⊗A−→ Ais a morphism of dg modules. Remark 2.1.16. Notice that if (A, ∂, µ) is a DGA, then A0must be an algebra with associative multiplication µ:A0⊗A0−→ A0. Definition 2.1.17. Aderivation of degree kon a graded algebra (A, µ) is a degree kgraded map d:A−→ Asatisfying the Leibniz rule d(ab) = d(a)b+ (−1)k|a|ad(b) for all homogeneous a, b ∈A. By induction, this implies d(a1. . . an) = n X i=1 (−a)|a1|+...+|ai−1|a1. . . d(ai). . . an for all homogeneous a1, . . . , an∈A. 2.1. Differential graded (co)algebras 51 Let (A, ∂) be a dg module and (A, µ) be a graded coalgebra. If we denote also by ∂the differential on A⊗A, then ∂is a derivation on (A, µ) if and only if µis a morphism of dg modules, which is equivalent to (A, ∂, µ) forming a DGA. Definition 2.1.18. Amorphism of DGAs f: (A, ∂, µ)−→ (A0, ∂0, µ0) is a dg morphism f: (A, ∂)−→ (A0, ∂0) that is also a morphism of graded algebras f: (A, µ)−→ (A0, µ0). Definition 2.1.19. The cohomology DGA of a DGA (A, ∂, µ) with |∂|= 1 is the DGA (H∗(A),0, µ∗), i.e., with zero differential and with the multiplication induced in cohomology. Every morphism of DGAs induces a morphism of DGAs between the corresponding cohomology DGAs. We next present dual definitions to some of the ones just listed. Definition 2.1.20. Agraded coalgebra (C, ∆) is a graded module C equipped with a morphism of graded modules ∆: C−→ C⊗C (called comultiplication or coproduct) that is coassociative, i.e., such that the following diagram commutes C∆// ∆  C⊗C 1⊗∆  C⊗C∆⊗1//C⊗C⊗C, 52 Chapter 2. A∞-structures Definition 2.1.21. Given graded coalgebras (C, ∆) and (C0,∆0), a morphism of graded coalgebras from Cto C0 f: (C, ∆) −→ (C0,∆0) is a graded morphism that is comultiplicative, i.e., such that the following diagram commutes. Cf// ∆  C0 ∆0  C⊗Cf⊗f//C0⊗C0 Definition 2.1.22. Adifferential graded coalgebra (DGC) is a triple (C, ∂, ∆) in which (i) (C, ∂) is a dg module, (ii) (C, ∆) is a graded coalgebra, and (iii) ∆: C−→ C⊗Cis a morphism of dg modules. Remark 2.1.23. Notice that if (C, ∂, ∆) is a DGC, then C0must be a coalgebra with coassociative comultiplication ∆: C0−→ C0⊗C0. Definition 2.1.24. Acoderivation of degree kon a graded coalgebra (C, ∆) is a degree kgraded map d:C−→ Csuch that the following diagram commutes for all p∈Z Cp∆// d  (C⊗C)p d⊗1+1⊗d  Cp+k∆//(C0⊗C0)p+k. Let (C, ∂) be a dg module and (C, ∆) be a graded coalgebra. If we denote also by ∂the differential on C⊗C, then ∂is a coderivation on (C, ∆) if and only if ∆ is a morphism of dg modules, which is equivalent to (C, ∂, ∆) forming a DGC. 2.1. Differential graded (co)algebras 53 Definition 2.1.25. Amorphism of DGCs f: (C, ∂, ∆) −→ (C0, ∂0,∆0) is a dg morphism f: (C, ∂)−→ (C0, ∂0) that is also a morphism of graded coalgebras f: (C, ∆) −→ (C0,∆0). 2.1.1 Cup product and Alexander-Whitney diagonal Let Xbe a topological space. Its singular chain complex (C∗(X), ∂) has a standard DGA structure given by the cup product. Similarly, its singular cochain complex (C∗(X), δ) has a standard DGC structure given by the Alexander-Whitney diagonal as coproduct. This is no coincidence. In this section we recall the basic constructions that allow us to see some of the underlying connection between these operations. We will also point out that this has analogues in terms of simplicial, cellular and cubical complexes. The main two ingredients in the construction of the two operations are the diagonal map D:X−−−−→ X×X x7−−→ (x, x) and the Alexander-Whitney map AW :C∗(X×Y)−−−−→ C∗(X)⊗C∗(Y), that we will define next. The Alexander-Whitney diagonal is the composition ∆: C∗(X)D#//C∗(X×X)AW //C∗(X)⊗C∗(X) and the cup product is the composition ^:C∗(X)⊗C∗(X)×//C∗(X×X)D# //C∗(X), where ×denotes a cross product that can be defined through the map AW. 54 Chapter 2. A∞-structures The Alexander-Whitney map AW is a natural chain homotopy equivalence of the form AW :C∗(X×Y)−−−−→ C∗(X)⊗C∗(Y) for all spaces X, Y , whose chain homotopy inverse is the so called EilenbergZilber map [40]. This map is unique up to homotopy equivalence. In order to describe the map AW, let us set up some fairly common notation first. Let p∈Nand let ei= (0,...,0,1 i,0, . . . , 0) ∈Rp+1 for every 0 ≤i≤p. If we view the standard p-simplex as ∆p=(p X i=0 tiei∈Rp+1 |ti≥0,Xti= 1), then we can define maps fk: ∆k−→ ∆pand bl: ∆l−→ ∆p on the vertices by    fk(ei) = ei,for all 0 ≤i≤k bl(ei) = ei+p−l,for all 0 ≤i≤l and extend them by linearity. Thus the map fkembeds ∆kas the kdimensional front face of ∆pand blembeds ∆las the l-dimensinal back face of ∆p. Definition 2.1.26. Let X, Y be topological spaces. For any p∈N, the Alexander-Whitney map AW :Cp(X×Y)−−−−→ (C∗(X)⊗C∗(Y))p is the linear map defined on p-simplices σ: ∆p−→ X×Y 2.1. Differential graded (co)algebras 55 with projections σX: ∆pπXσ −−−−→ Xand σY: ∆pπYσ −−−−→ Y by AW (σ) = X k+l=p σXfk⊗σYbl. Definition 2.1.27. The Alexander-Whitney diagonal is the composition of the Alexander-Whitney map and the map induced by the diagonal. With the notation above, ∆:C∗(X)D#//C∗(X×X)AW //C∗(X)⊗C∗(X) for every space X. Explicitely, for any p∈N, and for any p-simplex σ: ∆p−→ X, ∆ (σ) = X k+l=p σfk⊗σbl. As we said before, we can also obtain the cup product out of the maps D and AW. Let us begin by defining a cross product C∗(X)⊗C∗(Y)−−−−→ C∗(X×Y) for all spaces Xand Y. Let k, l ∈Nand let α∈Ck(X), β ∈Cl(Y). We define the cross product of αand βas the composition Ck+l(X×Y) AW  α×β//R (C∗(X)⊗C∗(Y))k+l π//Ck(X)⊗Cl(Y)α⊗β//R⊗R, · OO where πis the projetion onto the indicated summand. Explicitely, for any (k+l)-simplex σ: ∆k+l−→ X×Y, (α×β) (σ) = α(σXfk)β(σYbl), and therefore, D#(α×β) (σ) = α(σfk)β(σbl) = (α ^ β) (σ). 56 Chapter 2. A∞-structures Hence, as mentioned at the beginning of this section, we can view the cup product as the composition ^:C∗(X)⊗C∗(X)×//C∗(X×X)D# //C∗(X). This section can be adapted to contexts other than singular. If we work with CW (resp., simplicial) complexes, then all can be done in a similar fashion by adding the use of cellular (resp., simplicial) approximations, and things keep being beautiful because no matter the approximations we choose, the result will be the same up to chain homotopy equivalence. The cubical case, interesting in some applications like digital imaging, is studied in [58] and [59]. 2.2 Basics of A∞-(co)algebras In this section we recall the basic facts we shall use from A∞-coalgebras and A∞-algebras. Definition 2.2.1. An A∞-coalgebra (C, {∆n}n≥1) consists of a graded module Cand a sequence of maps ∆n:C−→ C⊗n of degree n−2 such that, for all n≥1, the following so called Stasheff identity holds: SI(n): n X i=1 n−i X j=0 (−1)i+j+ij 1⊗n−i−j⊗∆i⊗1j∆n−i+1 = 0. Notice that when these formulas are applied to elements, additional signs appear due to Koszul’s convention (see Definition 2.1.5). Let us have a look at what they tell us for low values of n. SI(1) states that ∆1∆1= 0, meaning that we can see ∆1:C−→ C 2.3. Algorithmic approach 63 such that φ2= 0. Ahomology gvf is an algebraic gvf which satisfies φ∂φ =φand ∂φ∂ =∂. Example 2.3.2. Consider a filled square with the CW complex structure K givev by 0-cells c0, . . . , c3, 1-cells c4, . . . , c7and 2-cell c8as in Figure 2.1. c0c1 c3c2 c4 c6c5 c8 c7 Figure 2.1: A CW complex desomposition Kof a filled square. The following assignments define a homology gvf φon C∗(K;F2): φ(c0)=0, φ(c1) = c4, φ(c2) = c4+c5, φ(c3) = c6, φ(c4) = φ(c5) = φ(c6) = 0, φ(c7) = c8, φ(c8) = 0. Using Discrete Morse Theory pictorial language, a homology gvf can be expressed by means of arrows on the CW complex in the obvious manner. Figure 2.2 shows an example of this. c0c1 c3c2 c4 c6c5 c8 c7 Figure 2.2: Arrows describing the homology gvf φin Example 2.3.2. The information that a homology gvf gives is equivalent to that of a transfer diagram: 64 Chapter 2. A∞-structures Proposition 2.3.3. [80, Prop. 1] A homology gvf φ:C∗(K)−→ C∗(K) yields a transfer diagram φ<<(C∗(K), ∂)π//(Im π, 0) ι oo where •π:= 1C∗(K)−∂φ −φ∂ :C∗(K)−→ Im π, and thus (Im π, 0) becomes a chain subcomplex of C∗(K)isomorphic to H∗(K), and •ι:Im π−→ C∗(K)is the inclusion. Conversely, given a transfer diagram of the form φ<<(C∗(K), ∂)π//(H∗(K),0), ι oo φ:C∗(K)−→ C∗(K)is a homology gvf. We need a definition to understand the input of the algorithm. Definition 2.3.4. Let (K, ∂) be a finite CW complex with m+ 1 cells. A filter is an ordered list Km=hc0, . . . , cmi of the cells of Kso that, for all 0 ≤i≤m, the cells in the list Ki=hc0, . . . , cii, together with the boundary map ∂i(the restriction of ∂to those cells) form a subcomplex of K. In Persistence, the filter usually matters a lot, but if we do not care about the filter, a simple way to get one out of an arbitrary finite CW complex is to first consider all its 0-cells in a certain order, then add all its 1-cells in a certain order and so on. 2.3. Algorithmic approach 65 Given a finite finite CW complex (K, ∂) with m+ 1 cells, the input of Algorithm 2.3.5 is a filter Km=hc0, . . . , cmi and the boundary maps {∂i}0≤i≤mas above. And here is the algorithm, whose output will be a function φmdefined on every element of the list Km=hc0, . . . , cmi so that its linear extension φwill be a homology gvf on C∗(K): 66 Chapter 2. A∞-structures Algorithm 2.3.5.Our adjustment of Algorithm 1 in [80]. m H0:= {c0}; φ0(c0) := 0; For i= 1 to m: ¯ci:= ci+φi−1∂i(ci); Hi:= Hi−1∪ {¯ci}; φi(ci) := 0; If ∂i(¯ci)=0: For j= 0 to i−1: φi(cj) := φi−1(cj); End For; End If; If ∂i(¯ci)is a sum of the kind Pr j=1 uj6= 0 where each ujis a different element of Hi−1: Choose one of the summands ujand let kbe the subindex j of the chosen one; ˜ φ(uk) := ¯ci; ˜ φ(u) := 0 for every u∈ Hi−1− {uk}; For j= 0 to i−1: φi(cj) = (φi−1+˜ φ(1Ki+φi−1∂i−1+∂i−1φi−1))(cj); End For; Hi:= Hi− {uk,¯ci}; End If; End For; END; 2.3. Algorithmic approach 67 Table 2.3.6. Here is a list with the changes made to Algorithm 1 in [80]. The lines refer to the lines in Algorithm 1 in [80], not to those in the algorithm above: Line in Change (Part I) Alg. 1 in [80] 1, 3 & 14 The computation of πi(cj) has been removed, for all i and j. Reason: The value of πi(cj) is not actually used in any step of the algorithm, and the final πobtained when the algorithm finishes is not the right one. Notice that one can compute it at the end, once one has the final φ, by setting π:= 1 −∂φ −φ∂. 5 & 8 (∂i+∂i−1φi−1∂i)(ci) has become ∂i(¯ci). Reason: Both things are the same, for ∂irestricted to Ki−1equals ∂i−1, and with this change we take advantage of ¯cihaving already been computed. 9ui∈ Hi−1has become uj∈ Hi−1. Reason: just a typo. 9Pr j=1 πi−1(esj) has been removed. Reason: The deleted part was just a reminder of the form that the elements in Hi−1have. 10 ˜ φ(uk) := cihas become ˜ φ(uk) := ¯ci. Reason: If not, we do not obtain as OUTOUT a homology gvf, but simply an algebraic gvf. After this table, we show an example where the original algorithm would fail in providing a homology gvf. 13 (φi−1+˜ φ(1Ki+φi−1∂i−1+∂i−1φi−1)(cj) has become (φi−1+˜ φ(1Ki+φi−1∂i−1+∂i−1φi−1))(cj). Reason: Bracket missing. This table continues on the next page. 68 Chapter 2. A∞-structures Line in Change (Part II) Alg. 1 in [80] 15 The line has been placed inside (and at the end of) the last If clause. Reason: If not, whatever happened inside the two If, we would always do Hi:= Hi− {uk,¯ci}after having set, in line 4, Hi:= Hi−1∪ {¯ci}.This would mean the effect of a loop of the biggest For would always be equivalent to simply setting Hi:= Hi−1− {uk},leaving the homology Hiwith the only possibilities of remaining like Hi−1or decreasing its dimension in 1. As the second comment on line 10 says, without the appropriate change, we would obtain algebraic gvf’s, in general, but not homology gvf’s. Here is an example of this. Consider the filtered simplicial complex (K, ∂) with filter K4=h[0] ,[1] ,[2] ,[1,2] ,[0,2]i. Using Algorithm 1 in [80], once we correct the typo in line 9 and the little mistake pointed out about line 15, if we do not correct what we remarked about line 10, then will not get a homology gvd, but simply one of the following algebraic gvf φ4. Specifically, •We will get H4={c0}, φ4(c0) = 0, φ4(c1) = c4, φ4(c2) = c3+c4, φ4(c3) = 0, φ4(c4) = 0, if we choose uk:= c1, •and we will get H4={c1}, φ4(c0) = c4, φ4(c1) = 0, 2.3. Algorithmic approach 69 φ4(c2) = c3, φ4(c3) = 0, φ4(c4) = 0, if we choose uk:= c0. These changes in the algorithm make us get as output a homology gvf on C∗(K), which gives a transfer diagram φ<<(C∗(K), ∂)π//(Im π, 0) ι oo where (Im π, 0) is a dg module isomorphic to (H∗(K),0) (see Proposition 2.3.3), so we can use the following formulas, that can be deduced using the Basic Perturbation Lemma. Proposition 2.3.7. [52], [60], [57, Theorem 3.2]. Let (C, ∂C,∆) and (M, ∂M) be a simply connected DGC and a dg module, respectively, and let φ<<(C, ∂C)π//(M, ∂M) ι oo be a transfer diagram between them. Then Mis endowed with an A∞- coalgebra structure given by the morphisms ∆1=−∂M ∆n= (−1)[n/2]+n+1π⊗n∆(n)φ[⊗n−1]∆(n−1) · · · φ[⊗2]∆(2)ι, n ≥2 where ∆(k)= k−2 X i=0 (−1)i1⊗i⊗∆⊗1⊗k−i−2:C⊗k−1−→ C⊗k and φ[⊗k]:= k−1 X j=0 1⊗j⊗φ⊗(ιπ)⊗k−1−j:C⊗k−→ C⊗k, for all k≥2. Example 2.3.8. Consider the CW decomposition of the torus shown in Figure 2.3. Since the boundary of each cell is zero, the homology gvf that Algorithm 2.3.5 produces is φ= 0. Applying the formulas in Proposition 2.3.7, we get a good A∞-coalgebra {∆n}non the homology of the torus, where ∆2is the Alexander-Whitney diagonal and ∆n= 0 for all n6= 2. In particular, this proves that the torus is a formal space. 70 Chapter 2. A∞-structures c0c0 c0c0 c1 c2c2 c3 c1 Figure 2.3: The simplest CW decomposition of the torus, consisting of one 0-cell, two 1-cells and one 2-cell. Here arrows do not represent a discrete vector field, but the identifications of the top and bottom faces of the square (both are the cell c1) and of the left and right faces of the square (both are the cell c2), respectively. 2.4 The power of A∞-structures In Chapter 3 we want to use A∞-(co)algebras to improve the discriminatory power of persistence, that in its most basic form yields information at the level of Betti numbers. In this section we want to stress the power of A∞- structures over that of Betti numbers and even over that of DGAs and DGCs. We will start by proving Theorem 2.4.4, that along with Example 2.4.5, exhibits the existence of spaces with isomorphic homology groups and cohomology algebras but non-isomorphic good A∞-coalgebras on their homologies. To close this section, we name a classical argument (Theorem 2.4.6) that also makes our point in terms of A∞-algebras, in relation with the cohomology ring of loop spaces H∗(ΩX). Notice that in Section 3.2 we will give more results reinforcing the idea of the strength of A∞-structures. Let us recall a couple of definitions that will simplify the proof of Theorem 2.4.4. We refer the reader to the Appendix, which contains the notation and basic tools we will use from rational homotopy theory. Definition 2.4.1. An A∞-coalgebra (C, {∆n}n) such that ∆n= 0 for all n > 2 is called trivial. Definition 2.4.2. A minimal A∞-coalgebra is called degenerate if it is isomorphic to a trivial one. 2.4. The power of A∞-structures 71 Definition 2.4.3. A space Xis called formal if a (and therefore any) good A∞-coalgebra on H∗(X) induced by Xis degenerate. Here is the main result we proof in this section: Theorem 2.4.4. Let Xbe a non-formal simply connected CW complex of finite type and let Ybe the formal space associated to H∗(X;Q). Then, X and Yhave isomorphic rational homology groups and isomorphic rational cohomology algebras but their rational homologies do not admit isomorphic good A∞-coalgebra structures. Proof. Obviously, both spaces have isomorphic rational cohomology algebras, and in particular, isomorphic rational homology H∗(X, Q)∼ =H∗(Y, Q) which we will denote by V. Now, since Yis formal, every good A∞-coalgebra on Vinduced by Yis degenerate, i.e., isomorphic to a trivial one. On the other hand, since Xis non-formal, no good A∞-coalgebra on Vinduced by Xcan be isomorphic to a trivial one. Therefore, no good A∞-coalgebra on H∗(X, Q) (induced by X) can be isomorphic to a good A∞-coalgebra on H∗(Y, Q) (induced by Y). We now exhibit an example of spaces Xand Yas in the theorem above: Example 2.4.5. An explicit example given by the Theorem above is the following. Consider X= (S3∨S3)(5) to be the 5th Postnikov stage of the wedge S3∨S3. Its rational cohomology can be easily computed via Sullivan approach to rational homotopy theory to yield, H∗(X;Q)∼ =H∗(Λ(x3, y3, z5), d), where Λ(x3, y3, z5) denotes the free commutative (in the graded sense) algebra generated by two elements x3, y3of degree 3 and one element z5of degree 5; the differential dis zero on x3, y3and dz5=x3y3. A straightforward computation shows that this cohomology algebra has a basis (as graded vector space) {1, α3, β3, γ8, ρ8, ξ11} 72 Chapter 2. A∞-structures in which subscripts denote degree, and the only non trivial products are α3ρ8=−β3γ8=−ξ11. A standard argument in rational homotopy theory shows that, if Yis the formal space associated to this cohomology algebra, the rational homotopy of Yis infinite dimensional contrary to the behaviour of Xand thus, they do not have the same rational homotopy type. This shows that Xis non-formal and the theorem above applies. Last we mention a classical result due to T. Kadeishvili, this time in terms of A∞-algebras. To show that any good A∞-algebra on the cohomology of a space carries in general more information than simply the cohomology ring, we can notice that under mild conditions on X, any such good A∞- algebra determines the cohomology of its loop space, H∗(ΩX), whereas the cohomology ring of Xalone does not. Theorem 2.4.6. [60, Proposition 2] Let Xbe a simply connected space such that all its homology groups are free. Then, the homology of the bar construction (which is the dual of Definition 2.2.5) of any good A∞-algebra on H∗(X)is isomorphic to the cohomology of the loop space of X. 3.2. Backing our stand 79 and dim Ker ∆kare invariants of the isomorphism class of minimal A∞- coalgebras structures {∆n}non a graded module C(e.g., C=H∗(X)). This might be a folklore result in rational homotopy theory but since we have not been able to find a proof of it, we provide one here. Theorem 3.2.2. Let Cbe a graded module and let {∆n}nand {∆0 n}nbe two isomorphic minimal A∞-coalgebra structures on Csuch that there exist some m, m0≥1for which ∆m6= 0 and ∆0 m06= 0. Then, the numbers k:= min{n|∆n6= 0}and min{n|∆0 n6= 0} coincide, (C, {0, . . . , 0,∆k,0, . . .})and (C, {0, . . . , 0,∆0 k,0, . . .}) are isomorphic A∞-coalgebras and the numbers dim Ker ∆k|Cpand dim Ker ∆0 k|Cp coincide too, for all p≥0. This turns out to be very useful for us because we are interested in computing good A∞-coalgebra structures on H∗(X), which are all minimal and therefore isomorphic in view of Theorem 2.2.9. Theorem 3.2.2 yields the following corollary: Corollary 3.2.3. Let {∆n}nand {∆0 n}nbe two arbitrary good A∞-coalgebra structures on the homology of a space Xsuch that there exist some m, m0≥1 for which ∆m6= 0 and ∆0 m06= 0. Then, the numbers k:= min{n|∆n6= 0}and min{n|∆0 n6= 0} coincide, (H∗(X),{0, . . . , 0,∆k,0, . . .})and (H∗(X),{0, . . . , 0,∆0 k,0, . . .}) are isomorphic A∞-coalgebras and the numbers dim Ker ∆k|Hp(X)and dim Ker ∆0 k|Hp(X) coincide too, for all p≥0. 80 Chapter 3. A∞-persistence First we prove a preliminary result. Lemma 3.2.4. Let (C, {∆n}n)be an A∞-coalgebra such that ∆n6= 0 for some n≥1. If we denote by kthe lowest integer n≥1such that ∆n6= 0, then (C, {0, . . . , 0,∆k,0, . . .}) forms an A∞-coalgebra too. Proof. Let (C, {∆n}n) and kbe as in the statement and define ∆0 n:=    0, n 6=k; ∆k, n =k. Let us denote by SI(1),SI(2), . . . , SI(n), . . . the Stasheff identities (Definition 2.2.1) on {∆n}nand by SI0(1),SI0(2), . . . , SI0(n), . . . the Stasheff identities on {∆0 n}n. (C, {∆0 n}n) forms an A∞-coalgebra if and only if the identities SI0(n) hold for all n≥1. Notice that all of them except for SI0(2k−1) become the trivial identity 0 = 0,and that SI0(2k−1) becomes k+1 X j=0 (−1)k+j+kj 1⊗k−1−j⊗∆k⊗1j∆k= 0, since this is the only SI0(n) in which ∆kcomposes with ∆k(tensored by identities), the only non-zero operation in {∆0 n}. Let us now look at the identity SI(2k−1) on {∆n}n. If some ∆nwith n > k appears in SI(2k−1), then ∆n(or ∆ntensored by identities) is pre or post composed with ∆mfor some m < k (or with ∆mtensored by identities). Since ∆m= 0, such a composition vanishes. Therefore, SI(2k−1) coincides with SI0(2k−1). Since we know that (C, {∆n}n) forms an A∞-coalgebra and hence that SI(2k−1) holds, this means that SI0(2k−1) holds too. 3.2. Backing our stand 81 With this, we have shown that (C, {∆0 n}n) satisfies all Stasheff identities and thus forms an A∞-algebra. We devote the rest of this section to proving Theorem 3.2.2, for which we will make use of the algebraic Milnor-Moore spectral sequence. The background on spectral sequences needed to follow the proof can be found in Sections 18 and 23(b) in [41] and Chapter 1 in [51]. Let (C, {∆n}n) be a minimal A∞-coalgebra and ΩC= ( b T(s−1C), d) its cobar construction (Def. 2.2.5). Let us recall that we can write d=Pn≥1dn,where each dn:b T(s−1C)−→ T≥n(s−1C) = Πp≥nTp(s−1C) satisfies dnTp(s−1C)⊆Tp+n−1(s−1C) for all p∈Nand acts on T1(s−1C) = s−1Cas the composition dn:s−1Cs//C−(−1) n(n−1) 2∆n//C⊗n(s−1)⊗n //Tn(s−1C). Let us denote by kthe integer k:= min{n|∆n6= 0}, which is obviously equal to min{n|dn6= 0}. Since (C, {∆n}n) is minimal, the number kmust be at least 2. Let us consider another minimal A∞-coalgebra (C, {∆0 n}n) isomorphic to (C, {∆n}n) and write d0=Pn≥1d0 nas before. This means that if we denote by Ω0C= ( b T(s−1C), d0) 82 Chapter 3. A∞-persistence the cobar construction of (C, {∆0 n}n), then ΩCand Ω0Care isomorphic as DGA’s. We will prove that if we set k0:= min{n|∆0 n6= 0}(= min{n|d0 n6= 0}), then k=k0and the DGA’s ( b T(s−1C), dk) and ( b T(s−1C), d0 k) are isomorphic. Assume k≤k0and let b T(s−1C) = F0⊇F1⊇. . . ⊇Fp⊇Fp+1 ⊇. . . be the word-length filtration of ΩC,i.e., for all p∈N,Fpis the differential ideal given by Fp=T≥p(s−1C). In the algebraic Milnor-Moore spectral sequence, E0is the graded algebra associated to this filtration, i.e., for all p∈N, Ep 0=Fp Fp+1 ∼ =Tp(s−1C) and E0=M p∈N Ep 0∼ =T(s−1C). The differential ∂0=M p∈N ∂p 0:E0−→ E0 is the map induced by d, thus for all p∈N, ∂p 0:Ep 0−→ Ep 0 must be d1:Tp(s−1C)−→ Tp(s−1C), which is 0, for Cis minimal. Altogether, (E0, ∂0)∼ =(b T(s−1C),0). 3.2. Backing our stand 83 In the algebraic Milnor-Moore spectral sequence, for all p∈Nwe have Ep 1∼ =Ep 0∼ =Tp(s−1C), and the map ∂p 1:Ep 1−→ Ep+1 1 induced by dis thus d2:Tp(s−1C)−→ Tp+1(s−1C). Hence, (E1, ∂1)∼ =(b T(s−1C), d2). Actually, we can easily verify that (E0, ∂0)∼ =. . . ∼ =(Ek−2, ∂k−2)∼ =(b T(s−1C),0) and (Ek−1, ∂k−1)∼ =(b T(s−1C), dk). The following result is a version of Theorem I in Section 1.3 in [51] in terms of DGA’s. Theorem 3.2.5. [51, Theorem I in Section 1.3] (Comparison theorem) Let ϕ:M−→ M0a filtered morphism of DGA’s whose spectral sequences are convergent. Then, if there is some i∈Nsuch that the induced map Ei(ϕ): Ei(M)−→ Ei(M0) is an isomorphism of DGA’s, then so are the maps Ej(ϕ): Ej(M)−→ Ej(M0), for all j≥i, and so is the map H∗(ϕ): H∗(M)−→ H∗(M0). 84 Chapter 3. A∞-persistence Let ϕ: ΩC−→ ΩC0 be an isomorphism of DGA’s, that exists because (C, {∆n}n) and (C, {∆0 n}n) are isomorphic A∞-coalgebras. Since ϕis filtered, it induces a morphism of spectral sequences {Er(ϕ)}r from the algebraic Milnor-Moore spectral sequence associated to ΩCto that associated to Ω0C. Recall that the linear part of ϕ, ϕ1:s−1C−→ s−1C, is defined by ϕ(s−1c) = ϕ1(s−1c) + Φ, where Φ ∈T≥2(s−1C). Since ϕ is an isomorphism, ϕ1must also be an isomorphism. Now observe that E0(ϕ) = Ek−2(ϕ) is precisely the isomorphism b T(ϕ1): ( b T(s−1C),0) −→ (b T(s−1C),0). Applying the comparison criterion, we get that Ek−1(ϕ): T(s−1C), dk−→ T(s−1C), d0 k is an isomorphism of DGA’s. In particular, d0 kcannot be zero. Hence k=k0 and the first claim in Theorem 3.2.2 holds. For the second claim, that the A∞-coalgebras (we know they are indeed A∞-coalgebras thanks to Lemma 3.2.4) (C, {0, . . . , 0,∆k,0, . . .}) and (C, {0, . . . , 0,∆0 k,0, . . .}) are isomorphic, simply observe that the corresonding cobar constructions are ( b T(s−1C), dk) and ( b T(s−1C), d0 k) which we have just seen are isomorphic DGA’s via Ek−1(ϕ). Finally, this tells us there exists an isomorphism of A∞-coalgebras f: (C, {0, . . . , 0,∆k,0, . . .})−→ (C, {0, . . . , 0,∆0 k,0, . . .}). 3.2. Backing our stand 85 The morphism identity MI(k) (see Def. 2.2.6) becomes ∆0 kf(1) =f(1)⊗k∆k. Since f(1) is an isomorphism, this implies that dim Ker ∆k|Cp= dim Ker ∆0 k|Cp for all p≥0. 3.2.3 Massey products In this section we will recall the notion of Massey products and give some reasons why we might want to have them in mind when computing Persistence of A∞-structures the way we do it. The triple and generalized Massey products were first introduced in [99] and [70], respectively, and a most clear general exposition of this topic can be found in [74]. Let (A, d, µ) be a DGA with |d|= 1. For our purposes, we may think of the usual singular cochain DGA of a space (C∗(X), δ, ^). Let us consider its cohomology algebra (H∗(A), µ∗), use the notation ab to denote either µ(a⊗b) or µ∗(a⊗b),and let a:= (−1)|a|+1a for any homogeneous a∈A. The triple Massey product is only defined on classes [u],[v],[w]∈H(A) such that    [u][v] = 0 [v][w] = 0. Fixing such classes, if [u]∈Hp(A),[v]∈Hq(A),[w]∈Hr(A), let us choose u∈Ap, v ∈Aq, w ∈Arrepresenting [u],[v],[w], respectively. Since [u][v] = 0, there exists some s∈Ap+q−1such that ds =uv. Analogously, since [v][w] = 0, there exists some t∈Aq+r−1such that dt =vw. We can form the element sw +ut ∈Ap+q+r−1, 86 Chapter 3. A∞-persistence which satisfies d(sw +ut) = 0, so we can consider its cohomology class [sw +ut]∈Hp+q+r−1(A). Notice that, in order to create this cohomology class out of [u],[v],and [w], we have made 5 choices; namely, representants u, v, w and elements s, t. The triple Massey product of [u],[v],[w], denoted by h[u],[v],[w]i, is defined as the set of all possible classes of the form [sw +ut]∈Hp+q+r−1(A), where u, v, w, s, t vary over all possible choices as just explained. Hence, h[u],[v],[w]iis a subset of Hp+q+r−1(A). It is sometimes handy to see this as a single element in a group rather than as a subset. In this sense, it is easy to check that h[u],[v],[w]iis an element of the quotient group Hp+q+r−1(A) [u]Hq+r−1(A) + Hp+q−1(A)[w].(3.2.1) An important idea is when we say that a Massey product vanishes (or equivalently, that it is trivial). Definition 3.2.6. If the triple Massey product h[u],[v],[w]iis defined, we say that it is trivial (or vanishing) if the class it represents in the quotient (3.2.1) is the zero class, or equivalently, if 0 ∈Hp+q+r−1(A) is an element of the set h[u],[v],[w]i. We say that the triple Massey product of (A, d, µ) is trivial (or vanishing) if whenever the triple Massey product of three classes is defined, it is trivial. 3.2. Backing our stand 87 We have just shown how to define a 3-fold product set whenever certain 2fold products vanish (namely, when some cohomology products are 0). Now we are going to show how to define a 4-fold product set whenever certain 3-fold products vanish (namely, when some triple Massey products contain the 0 class). Let [u],[v],[w],[x]∈H∗(A) be such that the triple Massey products h[u],[v],[w]i,h[v],[w],[x]i are defined and both contain 0. This means that there exist representatives u, v, w, x of [u],[v],[w],[x], respectively, and homogeneous elements t0, t1, t2, Y1, Y2∈A, such that dt0=uv, dt1=vw, dt2=wx and dY1=t0w+ut1, dY2=t1x+vt2. Then, duY2+t0t2+Y1x= 0 and therefore [uY2+t0t2+Y1x]∈H|u|+|v|+|w|+|x|−2(A). We define the 4-fold Massey product of the classes [u],[v],[w],[x], denoted by h[u],[v],[w],[x]i, as the set of all cohomology classes of the form [uY2+t0t2+Y1x] that can be formed by letting the representatives u, v, w, x and the homogeneous elements t0, t1, t2, Y1, Y2vary over all possible choices as just described. More generaly, we can define an n-fold product whenever certain (n−1)- fold products vanish (in the sense, as before, that they contain the 0 class). Definition 3.2.7. [67] Fix some n≥3 and let [αi]∈Hpi(A) for all 1 ≤i≤ n. A defining system associated to [α1],...,[αn] is a set {aij}1≤i≤j≤n,(i,j)6=(1,n)⊆A satisfying, for all 1 ≤i≤j≤nwith (i, j)6= (1, n), the following: 88 Chapter 3. A∞-persistence (i) aij ∈Api+pi+1+...+pj+(i−j), (ii) aii is a representative of [αi] in Hpi(A), (iii) d(aij) = Pj−1 r=iairar+1,j. To a defining system we associate the cocycle n−1 X r=1 a1rar+1,n ∈Ap1+...+pn+(2−n). The n-fold Massey product of the classes [α1],...,[αn] is denoted by h[α1], . . . , [αn]i and defined as the set of cohomology classes of cocycles associated to all possible defining systems for [α1],...,[αn]. This indeed generalizes the definitions for n= 3,4 given above. For n= 3, a choice of u, v, w, s, t amounts to a defining system where     a11 a12 a22 a23 a33    =    u s v t w    . For n= 4, a choice of u, v, w, x, t0, t1, t2, Y1, Y2amounts to a defining system where       a11 a12 a13 a22 a23 a24 a33 a34 a44      =      u t0Y1 v t1Y2 w t2 x      . We define triviality for an arbitrary nin a similar fashion as we did for the triple product. Definition 3.2.8. If the n-fold Massey product h[α1],...,[αn]iis defined, we say that it is trivial (or vanishing) if the set h[α1],...,[αn]icontains the zero class. 3.3. A first decomposition result 95 Definition 3.3.3. For every 0 ≤i≤j≤N,p≥0 and n≥1, we define the pth ∆n-persistence group between Kiand Kjas the vector space (∆n)i,j p(K)= Im fi,j p|∩j k=iKer(∆k n◦fi,k p). We note that this definition includes that of classical persistence groups (see Def. 1.2.3): Proposition 3.3.4. (∆1)i,j p(K) = Hi,j p(K)for all 0≤i≤j≤Nand p≥0. Proof. Since ∆k 1= 0 for each k, we have (∆1)i,j p(K) = Im fi,j p=Hi,j p(K). It is obvious from the definition of the classical persistence groups that for any basis Bof LN i=0 Hp(Ki), dim Hi,j p(K) = #       β∈ B ∩Hp(Ki) there exist some 0 ≤k≤iand α∈Hp(Kk) such that β=fk,iα and αis alive at least from Kito Kj        for all 0 ≤i≤j≤Nand p≥0. Checking whether a class is alive is computationally costly because it involves checking whether it has merged with an older class. So the fundamental theorem of persistent homology, Theorem 1.2.8, tells us that there exists a basis Bof LN i=0 Hp(Ki) that allows the much simpler computation dim Hi,j p(K) = #{β∈ B ∩Hp(Ki)|fi,kβ6= 0 for all k=i, . . . , j}, or even simpler, dim Hi,j p(K) = #{β∈ B ∩Hp(Ki)|fi,jβ6= 0}, for all 0 ≤i≤j≤Nand p≥0. On the other hand, concerning ∆n-persistence (fixed n≥1), if we choose a basis of Ker ∆i n|Hp(Ki)for each iand p, put them together to form a basis 96 Chapter 3. A∞-persistence of LiKer ∆i n|Hp(Ki)and enlarge this one to get a basis Bof LN i=0 Hp(Ki), then dim(∆n)i,j p(K) = #                β∈ B ∩Hp(Ki)  there exist some 0 ≤k≤iand α∈Hp(Kk) such that β=fk,iα and αis ∆n-awake at least from Kito Kj                (3.3.3) for all 0 ≤i≤j≤Nand p≥0. Now, similarly to the classical case, checking if a class is ∆n-awake is computationally costly. It is actually more costly than simply checking if it is alive, so a result that guarantees that we can simplify computations in the style of Theorem 1.2.8 is most needed. Indeed, we can prove the following. Theorem 3.3.5. Fix some integers p≥0and n≥1. If fi,i+1 p(Ker ∆i n)⊆ Ker ∆i+1 nfor all 0≤i<N, then there exists a basis Bof LN i=0 Hp(Ki)such that dim(∆n)i,j p(K)=#{β∈ B ∩Hp(Ki)|fi,kβ∈Ker ∆k n−{0}for all k=i, . . . , j} for every 0≤i≤j≤N. Furthermore, this number equals #{β∈ B ∩Hp(Ki)|fi,jβ∈Ker ∆j− {0}}. Proof. Fix a good A∞-coalgebra structure {∆i n}non H∗(Ki), for all 0 ≤i≤ Nand fix two integers n≥1 and p≥0. Let us simply denote by ∆ithe restriction of the map ∆i nto Hp(Ki), for all 0 ≤i≤N. If fi,i+1 Ker ∆i⊆Ker ∆i+1 (3.3.4) holds for all 0 ≤i < N, then the restriction of the maps in the persistence module Hp(K0)f0,1 p//Hp(K1)f1,2 p//. . .fN−1,N p//Hp(KN) 3.4. Coherent choices of A∞-structure 97 yields the persistence (sub)module Ker ∆0f0,1 p//Ker ∆1f1,2 p//. . .fN−1,N p//Ker ∆1.(3.3.5) Applying Lemma 1.2.7 to (3.3.5), we get that there exists a basis B0of LiKer ∆isuch that dim Hi,j p(K) = #{β∈ B0∩Hp(Ki)|fi,jβ6= 0}(3.3.6) for all i, and if we enlarge B0to a basis Bof LiHp(Ki), then the term on the right hand side in (3.3.6) coincides with #{β∈ B ∩Hp(Ki)|fi,jβ∈Ker ∆j− {0}}, or equivalently (using (3.3.4)), with #{β∈ B ∩Hp(Ki)|fi,kβ∈Ker ∆k− {0}for all k=i, . . . , j}. In §3.5 we show (along with the potentially intermittent behaviour of homology classes with respect to A∞-persistence) that the assumption fi,i+1 pKer ∆i n⊆Ker ∆i+1 n(3.3.7) in Theorem 3.3.5 does not always hold, and we devote §3.6 to stating and proving a result establishing that there is always a barcode decomposition to describe the p-homology classes that are ∆n-awake along the sequence K, regardless of the assumption (3.3.7) holding or not. 3.4 Coherent choices of A∞-structure Under certain conditions, we can guarantee that the assumption fi,i+1 Ker ∆i n⊆Ker ∆i+1 n of Theorem 3.3.5 will hold. 98 Chapter 3. A∞-persistence Theorem 3.4.1. With coefficients over the rationals Q, let K0be a 1connected CW complex and let Nbe an integer. If for all 0< i ≤N, Kidenotes a 1-connected space obtained attaching to Ki−1a cell such that dim M p≥0 Hp(Ki) = dim M p≥0 Hp(Ki−1)+1 (and hence every attachment produces new homology), then there exists a good A∞-coalgebra e H∗(Ki),{∆i n}nfor each 0≤i≤Nsuch that fi,i+1 Ker ∆i n⊆Ker ∆i+1 n, for every n≥1and 0≤i<N. Proof. First of all, notice that the hypotheses turn the maps fi,i+1 into inclusions. Start the construction by choosing any Quillen minimal model (L(V), ∂) of K0. Let K1=K0∪fem+1 be a 1-connected space obtained attaching an m+ 1-cell to K0via the map f:Sm→K0. The condition dim M p≥0 Hp(K1) = dim M p≥0 Hp(K0)+1 guarantees that the class [f]∈πm(K0)⊗Qis trivial, and hence so is the homology class in Hm−1(L(V), ∂) which is identified, via the isomorphism (ii) in the Appendix, with the homotopy class [f]. Therefore, since 0 ∈L(V)n−1 is a cycle representing the homology class [0] ∈Hn−1(L(V), ∂), Theorem 4.0.3 tells us that the injection (L(V), ∂),→(L(V⊕Qa), ∂0) with    ∂0v=∂v, for all v∈V ∂0a= 0 is a Quillen model of the inclusion K0,→K1. 3.5. Wake up every day (as long as you are alive) 99 Furthermore, since ∂0 1|V=∂1= 0 and ∂0a= 0, we have that ∂0 1= 0, so the model (L(V⊕Qa), ∂0) is indeed minimal. Applying this argument at each step, we get a Quillen minimal model (L(Vi), ∂i) for each Kiso that ∂i+1v=∂iv for any v∈Vi⊂Vi+1 and for all 0 ≤i < N. These Quillen minimal models then translate into good A∞-coalgebras e H∗(Ki),{∆i n}nsuch that for all n≥1 and 0 ≤i < N, ∆i+1 nα= ∆i nα for any α∈e H∗(Ki)⊂e H∗(Ki+1), and since the map fi,i+1 is an inclusion, this means that the equality ∆i+1 nfi,i+1 =fi,i+1⊗n∆i n holds and hence so does fi,i+1 Ker ∆i n⊆Ker ∆i+1 n. 3.5 Wake up every day (as long as you are alive) If we are not in the restrictive hypotheses of Theorem 3.4.1, there might not exist A∞-coalgebras on each H∗(Ki) such that fi,i+1 Ker ∆i n⊆Ker ∆i+1 n. Furthermore, even under the hypotheses of Theorem 3.4.1, if we do not follow the construction displayed in its proof, but allow instead more freedom in 100 Chapter 3. A∞-persistence the choice of the different A∞-structures, then they may fail to satisfy the assumptions fi,i+1 Ker ∆i n⊆Ker ∆i+1 n. Theorem 3.5.1 proves this claim and exhibits an intermittent behaviour that can take place when we have a lot of freedom to choose the different A∞-coalgebras. Namely, if fi,i+1 (Ker ∆i n)⊆Ker ∆i+1 ndoes not hold, then, by definition, a class that is ∆n-awake at Kican ∆n-fall asleep at Ki+1 without the need of dying at Ki+1. Moreover, Theorem 3.5.1 shows that classes can ∆n-fall asleep and ∆n-wake up several times along the filtration. This is, together with the fact that a class must be alive in order to be ∆n-awake, the reason why we chose the awake-asleep terminology. To prove Theorem 3.5.1, we will give an example of a class with such a behaviour using the rationals Qas field of coefficients. We refer the reader to the Appendix for the basics of rational homotopy theory. Let Kbe the filtration of finite complexes K0 i0 ,→K1 i1 ,→K2 i2 ,→K3 defined as follows: •K0= (S2 1∨S2 2∨S2 3∨S4)∪g1e6 1∪g2e6 2,in which S2 1,S2 2,S2 3simply denote three different copies of S2and the (homotopy classes of the) attaching maps for the 6-cells e6 1, e6 2are the following Whitehead products: g1= [idS4, idS2 1]+[idS2 1,[idS2 1,[idS2 1, idS2 2]]], g2= [idS4, idS2 2]. •K1=K0∪g3e4,in which g3= [idS2 1, idS2 2]. •K2=K1∪g4e6,in which g4= [idS4, idS2 1]−[idS2 2,[idS2 2,[idS2 2, idS2 3]]]. 3.5. Wake up every day (as long as you are alive) 101 •K3=K2∪g5e4,in which g5= [idS2 2, idS2 3]. •The maps i1, i2, i3are the inclusions. Then, we prove, Theorem 3.5.1. In H∗(K0;Q)f0 −→ H∗(K1;Q)f1 −→ H∗(K2;Q)f2 −→ H∗(K3;Q), all the morphisms are injective and we can give a good A∞-coalgebra structure to each term H∗(Ki;Q)so that the non zero homology class γ6∈H6(K0), created by the cell e6 1, is ∆4-asleep at K0, it ∆4-wakes up at K1, it is ∆4-asleep again at K2and finally, it ∆4-wakes up at K3. Proof. Via Theorem 4.0.3 of the Appendix, the following is a Quillen minimal model of K0(from now on, subscripts will always denote degree): (L(V0), ∂) = (L(x1, x0 1, x00 1, y3, z5, z0 5), ∂) where ∂x1=∂x0 1=∂x00 1=∂y3= 0, ∂z5= [y3, x1]+[x1,[x1,[x1, x0 1]]], ∂z0 5= [y3, x0 1]. Observe, either by direct computation or in light of the isomorphism (i) of the Appendix, that e H∗(K0;Q) = hα2, α0 2, α00 2, β4, γ6, γ0 6i=sV0. Next, a short computation shows that, in the universal enveloping algebra (T(V0), d) = U(L(V0), ∂) (see Appendix for its definition), d4z5=x1⊗x1⊗x0 1⊗x1+x1⊗x1⊗x1⊗x0 1−x0 1⊗x1⊗x1⊗x1−x1⊗x0 1⊗x1⊗x1. 102 Chapter 3. A∞-persistence In other words, in the A∞-coalgebra structure on H∗(K0;Q) given by (L(V0), ∂), ∆4γ66= 0, and thus, γ6is ∆4-asleep. Next, again by Theorem 4.0.3, a Quillen model of the inclusion i0:K0,→K1 is (L(x1, x0 1, x00 1, y3, z5, z0 5), ∂),→(L(x1, x0 1, x00 1, y3, y0 3, z5, z0 5), ∂), in which ∂y0 3= [x1, x0 1]. To describe in simpler terms the morphism induced in rational homology by the inclusion i0, consider the isomorphism of (non differential!) free Lie algebras ψ:L(x1, x0 1, x00 1, y3, y0 3, u5, z0 5)∼ = −→ L(x1, x0 1, x00 1, y3, y0 3, z5, z0 5) which sends u5to z5−[x1,[x1, y0 3]] and any other generator to itself. Then, set in the first free Lie algebra the differential ∂=ψ−1∂ψ so that ψbecomes an isomorphism of DGL’s. A short computation shows that the only generator on this isomorphic DGL in which the differential has changed is: ∂u5= [y3, x1]. To simplify the notation, set (L(V1), ∂) = (L(x1, x0 1, x00 1, y3, y0 3, u5, z0 5), ∂), and observe that the DGL morphism (L(V0), ∂)→(L(V1), ∂) 3.5. Wake up every day (as long as you are alive) 103 which sends z5to u5+ [x1,[x1, y0 3]], and any other generator to itself, is again a Quillen minimal model of i0:K0,→K1. In particular, the map induced by this morphism on the suspension of the indecomposables sV0→sV1is precisely the morphism f0=H∗(i0). Thus, on the one hand, f0:e H∗(K0;Q)−→ e H∗(K1;Q) is naturally identified to the inclusion sV0=hα2, α0 2, α00 2, β4, γ6, γ0 6i,→ hα2, α0 2, α00 2, β4, β0 4, η6, γ0 6i=sV1, for which f0(γ6) = η6. On the other hand, one sees that in the universal enveloping algebra (T(V1), d) = U(L(V1), ∂), du5=d2u5=y3⊗x1−x1⊗y3. Equivalently, in the A∞-coalgebra structure on H∗(K1;Q) given by (L(V1), ∂), ∆4η6= ∆4f0(γ6) = 0. In other words, the class γ6∆4-wakes up at K1. In the next stage, Theorem 4.0.3 produces a Quillen model of the inclusion i1:K1,→K2, (L(x1, x0 1, x00 1, y3, y0 3, u5, z0 5), ∂),→(L(x1, x0 1, x00, y3, y0 3, u5, z0 5, v5), ∂), in which ∂v5= [y3, x1]−[x0 1,[x0 1,[x0 1, x00 1]]]. Once again, to describe in simpler terms the morphism induced in rational homology by the inclusion i1, consider the isomorphism of (non differential!) free Lie algebras L(x1, x0 1, x00, y3, y0 3, w5, z0 5, v5)∼ = −→ L(x1, x0 1, x00, y3, y0 3, u5, z0 5, v5) 104 Chapter 3. A∞-persistence which sends w5to u5−v5and any other generator to itself. Then endow the left hand side free Lie algebra with the differential so that the above becomes an isomorphism of DGL’s. A short computation shows that the only generator on this isomorphic DGL in which the differential has changed is: ∂w5= [x0 1,[x0 1,[x0 1, x00 1]]]. Set (L(V2), ∂) = (L(x1, x0 1, x00 1, y3, y0 3, w5, z0 5, v5), ∂), and observe that the DGL morphism (L(V1), ∂)→(L(V2), ∂) which sends u5to w5+v5, and any other generator to itself, is a Quillen minimal model of i1:K1,→K2. In particular the map induced by this morphism on the suspension of the indecomposables sV1→sV2is precisely f1=H∗(i1). Thus, on the one hand, f1:e H∗(K1;Q)−→ e H∗(K2;Q) is naturally identified to the inclusion sV1=hα2, α0 2, α00 2, β4, β0 4, η6, γ0 6i,→ hα2, α0 2, α00 2, β4, β0 4, ρ6, γ0 6, γ00 6i=sV2, for which f1(η6) = ρ6. On the other hand, one sees that in the universal enveloping algebra (T(V2), d) = U(L(V2), ∂), dw5=x0 1⊗x0 1⊗x00 1⊗x0 1+x0 1⊗x0 1⊗x0 1⊗x00 1−x00 1⊗x0 1⊗x0 1⊗x0 1−x0 1⊗x00 1⊗x0 1⊗x0 1. Equivalently, in the A∞-coalgebra structure on H∗(K2;Q) given by (L(V2), ∂), ∆4ρ6= ∆4f0,1(γ6)6= 0. In other words, the class γ6∆4-falls asleep at K2. 3.6. A more general decomposition result 111 for all 1 ≤k≤land so that the lnumbers m(k) are all different. Applying the process just described to each of the llinearly independent classes in {α1, . . . , αl}will generate ldifferent intervals Imof the form I[a, b] with [2i, 2j]⊆[a, b]. This shows that dim(∆)i,j (K)≤Nij. A similar argument shows that Nij ≤dim(∆)i,j (K), and concludes the proof of Theorem 3.6.1. Definition 3.6.4. For every p≥0 and n≥1, we define the pth ∆n-barcode of Kas the multiset of intervals of the form [a, b]⊆R, with 0 ≤a≤b≤N, consisting of one [a, b] for each interval of either the form Im=I[2a, 2b−1] or the form Im=I[2a, 2b] in the decomposition V∼ =LmImof the zigzag module Vdescribed in the proof. With this definition, we can state a pleasant result in terms of similarity to the classical Theorem 1.2.4. Corollary 3.6.5. For every p≥0and n≥1, the pth ∆n-barcode of Kis well-defined and, for all 0≤i≤j≤N, the dimension of the persistent group (∆n)i,j p(K)equals the number of intervals in the pth ∆n-barcode of K (counted with multiplicities) which contain the interval [i, j]. In particular, dim Ker ∆i n|Hp(Ki)equals the number of intervals in the pth ∆n-barcode of K(counted with multiplicities) which contain i. Proof. The Zigzag’s Interval Decomposition Theorem (Theorem 1.3.1) says there is a the decomposition V∼ =LmImof the zigzag module Vdescribed in the proof of Theorem 3.6.1 and hence confirms that the pth ∆n-barcode of Kis well-defined. Remark 3.6.3 establishes that there is a bijection between the pth∆nbarcode of Kand the multiset of intervals Imin the decomposition V∼ = LmIm. Finally, the equality dim(∆)i,j (K) = Nij established in the proof of Theorem 3.6.1 corroborates the rest. 112 Chapter 3. A∞-persistence 3.7 Algorithmic approach At this point, it should be obvious how to compute A∞-persistence. Here is an abstract algorithm that takes as input integers n≥1, p≥0 and a filtration of CW complexes with finitely many cells K0//K1//. . .//KN, and produces the pth ∆n-barcode of the filtration given by some A∞-coalgebra structures computed during the algorithm. This algorithm will serve as a skeleton for the more concrete algorithms developed later. Algorithm 3.7.1.m 1. Compute a good A∞-coalgebra structure {∆i k}k≥1on H∗(Ki), for all 0≤i≤N; (e.g., through Algorithm 2.3.5, when applicable, as explained below); 2. Using the integers n≥1and p≥0from the input, apply the construction in the proof of Theorem 3.6.1 to obtain a zigzag module V; 3. Apply the zigzag decomposition algorithm (Algorithm 1.3.3) to V; 4. Apply the construction in Definition 3.6.4; If we work over the field of two elements F2, we can use Algorithm 2.3.5 to carry out step number 1, which is computing a good A∞-coalgebra {∆i k}k for each H∗(Ki). Since Algorithm 2.3.5 is already designed to work with filtrations, we can apply it simply once and get all the homology gradient vector fields φi:C∗(Ki)−→ C∗+1(Ki) we need to compute all those A∞-structures. Specifically, let n≥1 and p≥0 be integers and K0//K1//. . .//KN 3.7. Algorithmic approach 113 a filtration of CW complexes with finitely many cells. Order all cells in each Ki, denote the ordered cells of K0as e0 0, e1 0, . . . , ek0 0 and similarly, for each 0 < i ≤N, say that Kiconsists of the ordered cells in Ki−1plus the ordered cells e0 i, e1 i, . . . , eki i. Then, De0 0, e1 0, . . . , ek0 0, e0 1, e1 1, . . . , ek1 1, . . . , e0 N, e1 N, . . . , ekN NE forms a filter (Definition 2.3.4) and hence it can be used, along with the boundary maps induced by that of KN, as input for Algorithm 2.3.5. Finally, for all 0 ≤i≤N, since Ki=e0 0, e1 0, . . . , ek0 0, e0 1, e1 1, . . . , ek1 1, . . . , e0 i, e1 i, . . . , eki i, after running the step of Algorithm 2.3.5 in which the cell eki iis added, we get a homology gvf on C∗(Ki) and thus, using the formulae in Proposition 2.3.7, a good A∞-coalgebra on H∗(Ki). Chapter 4 Appendix: basics of rational homotopy theory In this appendix, for completeness, we recall the basic facts and classical results from rational homotopy theory used throughout the paper. For a compendium of this theory, we direct the reader to the standard reference [41]. Adifferential graded Lie algebra (DGL henceforth) is a differential graded vector space (L, ∂) in which: •L=⊕p∈ZLpin endowed with a linear operation, called Lie bracket, [,]: Lp⊗Lq−→ Lp+q, p, q ∈Z, satisfying antisymmetry, [x, y] = (−1)|x||y|+1[y, x], and Jacobi identity, x, [y, z]=[x, y], z+ (−1)|x||y|y, [x, z], for any homogeneous elements x, y, z ∈L. In other words, Lis a graded Lie algebra. 115 116 Chapter 4. Appendix: basics of rational homotopy theory •The differential ∂, of degree −1, satisfies the Leibniz rule, ∂[x, y] = [∂x, y] + (−1)|x|[x, ∂y], for any pair of homogeneous elements x, y ∈L. The tensor algebra T(V) = ⊕n≥0Tn(V) generated by the graded vector space Vis endowed with a graded Lie algebra structure with the brackets given by commutators: [a, b] = a⊗b−(−1)|a||b|b⊗a for any homogeneous elements a, b ∈T(V). Then, the free Lie algebra L(V) is the Lie subalgebra of T(V) generated by V. Observe that L(V) is filtered as follows, L(V) = ⊕n≥1Ln(V), in which Ln(V) is the vector space spanned by Lie brackets of length n, that is Ln(V) = L(V)∩Tn(V). In particular, to set a differential in L(V), it is enough to define linear maps, ∂n:V−→ Ln(V), n ≥1 in such a way that ∂=Pn≥1∂nsquares to zero and satisfies the Leibniz rule. Note that ∂1, the so called linear part of ∂, is therefore a differential in V. Remark 4.0.2. It is important to remark that, if T(V) is endowed with a derivation dfor which (T(V), d) is a differential graded (non commutative) algebra, L(V) does not inherit a differential as dmay not respect commutators. However, every time we have a DGL of the form (L(V), ∂), the differential ∂can be extended as a derivation of graded algebras to T(V) to make it a differential graded algebra. In other words, consider the functor U:DGL −→ DGA 117 which associates to every DGL (L, ∂) its universal enveloping algebra UL which is the graded algebra T(L)/h[x, y]−(x⊗y−(−1)|a||b|y⊗x)i, x, y ∈L, with the differential induced by ∂. Then, whenever (L, ∂)=(L(V), ∂), one has, U(L(V), ∂) = (T(V), ∂). In [87], D. Quillen associates to every 1-connected topological space X of the homotopy type of a CW complex, a particular differential graded Lie algebra (L(V), ∂) which is reduced, i.e., V=⊕p≥1Vpfor which: (i) H∗(V, ∂1)∼ =s−1e H∗(X;Q) = e H∗−1(X;Q). (ii) H∗(L(V), ∂)∼ =π∗(ΩX)⊗Q∼ =π∗+1(X)⊗Q. This is a Quillen model of Xand it is called minimal whenever ∂is decomposable, i.e., ∂1= 0. In this case, (i) becomes, V∼ =s−1e H∗(X;Q). The Quillen minimal model is unique up to isomorphism. Moreover, its construction is functorial and it defines an equivalence between the homotopy category of 1-connected spaces of the homotopy type of rational CW complexes and that of reduced differential graded Lie algebras over Q. Thus, two simply connected complexes have isomorphic Quillen minimal models if and only if they have the same rational homotopy type. In particular, if ϕ: (L(U), ∂U)→(L(V), ∂V) is the Quillen minimal model of the map f:X→Y, the morphism H∗(ϕ): H∗(L(U), ∂U)→H∗(L(V), ∂V) is naturally identified to π∗(Ωf): π∗(ΩX)→π∗(ΩY). In the same way, the morphism induced by ϕat the “indecomposables” ϕ0:U→Vis naturally identified to s−1H∗(f): s−1e H∗(X;Q)→s−1e H∗(Y;Q), the desuspension of the morphism induced by fin rational homology. To explicitly obtain ϕ0, write, for each u∈U,ϕ(u) = v+ Γ, with v∈Vand Γ ∈L≥2(V). Then ϕ0(u) = v. 118 Chapter 4. Appendix: basics of rational homotopy theory In the A∞-language, Remarks 4.0.2 and 2.2.4 together with the isomorphism (i) above, assert that e H∗(X;Q) can be functorially endowed with a structure of good A∞-coalgebra induced by any Quillen minimal model (L(V), ∂) of X. Given a 1-connected CW complex X, a (non necessarily minimal) Quillen model of Xcan be described in terms of a CW decomposition of Xvia the following, Theorem 4.0.3. [97, III.3.(6)] Let Y=X∪fen+1 be a 1-connected space obtained attaching an (n+1)-cell to Xvia the map f:Sn→X. Let (L(V), ∂) be a Quillen model of Xand let Φ∈L(V)n−1be a cycle representing the homology class in Hn−1(L(V), ∂)which is identified, via the isomorphism (ii) above, with the homotopy class [f]∈πn(X)⊗Q. Then, the injection (L(V), ∂),→(L(V⊕Qa), ∂0) with    ∂0v=∂v, for all v∈V ∂0a= Φ is a Quillen model of the inclusion X ,→Y. Finally, we recall that a simply connected complex is formal if its rational homotopy type depends only on its rational cohomology algebra. Given a commutative graded algebra Hthere is a formal simply connected complex X, unique up to rational homotopy, whose cohomology algebra H∗(X;Q) is isomorphic to H. Resumen en Espa˜nol Este trabajo es una mezcla entre dos mundos completamente distintos: Por un lado, la Homolog´ıa Persistente, un reci´en nacido de la generaci´on del An´alisis Topol´ogico de datos, y por el otro, las A∞-(co)´algebras, una piezas cl´asicas en la Teor´ıa de Perturbaci´on Homol´ogica. La Homolog´ıa Persistente (en el sentido de [23, 39, 103]), una t´ecnica topol´ogica que se ha aplicado con ´exito en contextos tan dispares como im´agenes digitales [89], redes de sensores [33], modelado molecular [3], sistemas din´amicos [38,88] y an´alisis del habla [15] entre muchos otros, permite extraer informaci´on global sobre la estructura de conjuntos de datos (especialmente complejos, que involucren muchas variables) que pueden contener peque˜nos errores (devido a la medici´on, por ejemplo). M´as de cerca, esta teor´ıa nos permite aproximar los n´umeros de Betti de un subconjunto cerrado desconocido Xde un espacio m´etrico a partir de una muestra finita de puntos de X[19,28,32,82,88]. En dimensiones bajas, estos n´umeros son a veces f´aciles de calcular a simple vista (como en Figure 4.1), pero una nube de puntos en un espacio 100-dimensional puede resultar dif´ıcil de visualizar. Adem´as, en tal situaci´on, nos tendr´ıamos que preocupar no s´olo de el n´umero de piezas (componentes conexas), t´uneles y cavidades del espacio Xsubyacente, sino tambi´en de rasgos 99-dimensionales, por ejemplo. ¿Por qu´e es esto ´util? Veamos un ejemplo. Imaginemos que queremos estudiar una enfermedad de la cu´al no sabemos mucho y para ello, empezamos por tomar 100 datos distintos de un paciente. Podemos ver estos n´umeros como coordenadas y visualizar los datos del paciente como un punto en un 119 120 Resumen en Espa˜nol Figure 4.1: Es f´acil ver a simple vista que ´esta puede ser una muestra de puntos de una corona circular. espacio eucl´ıdeo 100-dimensional E100. Repitiendo el proceso con 70000 personas obtenemos 70000 points in E100, donde cada punto representa a un paciente. Entonces, incluso si no le hacemos preguntas espec´ıficas al c´umulo de datos recopilados (bien porque no sepamos suficiente sober la enfermedad como para decidir qu´e preguntas hacer o bien porque no queramos que nuestro conocimiento previo condicione el tipo de informaci´on que podamos encontrar), la persistencia nos dar´a informaci´on topol´ogica sobre el espacio que se esconde tras la nube de puntos y esto puede ser traducido luego en informaci´on sobre la enfermedad en cuesti´on. N´otese que cuanto m´as sepamos sobre el espacio que se esconde tras la nube de puntos, m´as informaci´on conseguiremos acerca de tal enfermedad. El trabajo de la presente tesis se basa en esta observaci´on. M´as concretamente, como la Homolog´ıa Persistente, en su forma m´as b´asica, puede ´unicamente contribuir con informaci´on a nivel de los n´umeros de Betti, el desaf´ıo que puso en marcha este proyecto fue el de aumentar el poder de la persistencia encontrando herramientas que fueran capaces de distinguir, en diversas situaciones, entre espacios con los mismos n´umeros de Betti (e incluso con ´algebras de cohomolog´ıa isomorfas) que no fueran homot´opicamente equivalentes; herramientas que puedieran darnos informaci´on, en algunos casos, sobre c´omo est´an anudadas distintas componentes de un enlace; y lo m´as importante, herramientas que puedieran admitir un enfoque persistente. Resumen en Espa˜nol 127 en el cual la (clase de homotop´ıa de) la funci´on de adjunci´on ges el producto de Whitehead g= [idS2, idS2]. Estas estructuras son las inducidas, respectivamente, por dos modelos minimales de Quillen (v´ease el Ap´endice para los detalles) de X: por un lado, el ´algebra de Lie graduada diferencial (DGL) (L(W), ∂) = (L(x1, y3, z6), ∂), donde los sub´ındices denotan el grado y la diferencial viene dada por ∂x1= 0, ∂y3= [x1, x1], ∂z6= 2 [[x1, x1], y3]. Por otro lado, el DGL (L(V), ∂) = (L(x1, y3, u6), ∂), donde los sub´ındices denotan el grado y la diferencial viene dada por ∂x1= 0, ∂y3= [x1, x1], ∂u6= 0. En particular, la A∞-co´algebra inducida por (L(W), ∂) tiene ∆36= 0, mientras que la inducida por (L(V), ∂) tiene ∆3= 0. De hecho, esta ´ultima tiene ∆n= 0 para todo n > 2, lo que muestra que el espacio Xes formal sobre los racionales. 128 Resumen en Espa˜nol El mismo inconveniente ocurre con A∞-´algebras en H∗(X) y los n´umeros dim Coker mn|Hp1(X)⊗...⊗Hpn(X).Para superar este obst´aculo, probamos varios resultados que muestran escenarios en los que estos n´umeros pueden, a pesar de lo comentado, dar informaci´on m´as all´a de los n´umeros de Betti e incluso m´as all´a del ´algebra de cohomolog´ıa. Concretamente, primero demostramos el Teorema 3.2.2, un resultado que funciona cuando se trabaja sobre un cuerpo de caracter´ıstica 0, que implica en particular que los n´umeros k:= min{n|∆n6= 0} y dim Ker ∆k|Hp(X), para todo p≥0, son invariantes de la clase de isomorfismo de estructuras de A∞-co´algebra minimal {∆n}nen H∗(X). Una consecuencia importante de este resultado es el siguiente: Corolario 3.2.3. Sean {∆n}ny{∆0 n}ndos estructuras cualesquiera de A∞-co´algebra buena en la homolog´ıa de un espacio Xde modo que existan m, m0≥1para los cuales ∆m6= 0 y∆0 m06= 0. Entonces, los n´umeros k:= min{n|∆n6= 0}ymin{n|∆0 n6= 0} coinciden, (H∗(X),{0, . . . , 0,∆k,0, . . .})y(H∗(X),{0, . . . , 0,∆0 k,0, . . .}) son A∞-co´algebras isomorfas y los n´umeros dim Ker ∆k|Hp(X)ydim Ker ∆0 k|Hp(X) tambi´en coinciden, para todo p≥0. En la misma direcci´on, demostramos: Proposici´on 3.2.12. Denotemos por Llos anillos de Borromeo. Entonces, cualquier A∞-´algebra buena {mn}nen H∗(S3−L)cumplir´a m3|H1⊗H1⊗H16≡ 0, donde H1denota H1(S3−L). Resumen en Espa˜nol 129 Obs´ervese que podemos obtener resultados similares para mn|Hp1(X)⊗...⊗Hpn(X) con valores arbitrarios de n, p1, . . . , pn. En esta direcci´on, probamos tambi´en Proposici´on 3.2.13. Para enunciar ´esta, sean n=p+q+r,x= (x1, . . . , xp), y = (y1, . . . , yq),yz= (z1, . . . , zr) y consideremos tres espacios S1, S2, S3en Rn (homeomorfos a tres esferas) dados por las ecuaciones x= 0,kyk2+kzk2 4= 1 (esfera (q+r−1)-dimensional S1); y= 0,kzk2+kxk2 4= 1 (esfera (p+r−1)-dimensional S2); z= 0,kxk2+kyk2 4= 1 (esfera (p+q−1)-dimensional S3); N´otese que el caso p=q=r= 1 nos da unos anillos de Borromeo. En un cierto sentido m´as general que para el caso de nudos, estos espacios Siest´an no anudados dos a dos, lo que hace que el obvio producto de Massey est´e definido, y es m´as, denotando por Kla uni´on disjunta de S1, S2yS3, probamos lo siguiente: Proposici´on 3.2.13. Con esta notaci´on, cualquier A∞-´algebra buena {mk}k en H∗(Sn−K)deber´a cumplir m3|Hp⊗Hq⊗Hr6≡ 0, donde Hkdenota Hk(Sn−K). Todos estos resultados respaldan nuestro inter´es en el estudio de la persistencia de los mencionados n´umeros a lo largo de una filtraci´on, que pasamos a explicar a continuaci´on en t´erminos de A∞-co´algebras y homolog´ıa, aunque funciona tambi´en para A∞-´algebras and cohomolog´ıa. Sea K:K0//K1//. . . //KN una sucesi´on de espacios topol´ogicos y aplicaciones cont´ınuas. A la hora de palicarlo en el mundo real, en la mayor´ıa de los casos nos encontraremos con 130 Resumen en Espa˜nol una filtraci´on. Es decir, Kconsistir´a en subcomplejos simpliciales/c´ubicos/celulares anidados e inclusiones K0//K1//. . .//KN. Para cada p≥0 y 0 ≤i≤j≤N, supongamos que la dimensi´on del p-´esimo grupo de homolog´ıa de Kies finita, dim Hp(Ki)<∞, y denotemos por fi,j p:Hp(Ki)−→ Hp(Kj) y fi,j :H∗(Ki)−→ H∗(Kj) las aplicaciones inducidas en homolog´ıa por la composici´on. Ki//Ki+1 //. . . //Kj. La persistencia cl´asica describe, para cada p≥0, la evoluci´on del p-´esimo n´umero de Betti βp(X) = dim Hp(X) a lo largo de Kmediante el estudio de los llamados grupos persistentes Hi,j p(K) := Im fi,j p,0≤i≤j≤N. M´as concretamente, define un multiconjunto (un conjunto donde cada elemento tiene asociada una multiplicidad) de intervalos, llamado el p-´esimo c´odigo de barras (barcode), que satisface lo siguiente: Teorema 1.2.4. [23, §3] (Teorema Fundamental de la Homolog´ıa Persistente) Para cada p≥0, el p-´esimo c´odigo de barras de Kest´a bien definido y, para todo 0≤i≤j≤N, la dimensi´on del grupo persistente Hi,j p(K)es igual al n´umero de intervalos en el p-´esimo c´odigo de barras de K (contados con multilicidad) que contienen al intervalo [i, j]. En particular, dim Hp(Ki)es igual al n´umero de intervalos en el p-´esimo c´odigo de barras de K(contados con multilicidad) que contienen al valor i. En §1.2, damos una nueva demostraci´on de este resultado cl´asico. En particular, lo hacemos probando un Lema previo que tiene la siguiente forma. Resumen en Espa˜nol 131 Definici´on 1.2.6. Un m´odulo de persistencia es una sucesi´on finita de espacios vectoriales de dimensi´on finita y aplicaciones lineales entre ellos de la forma V0//V1//. . . //VN. Lema 1.2.7. Sea V0 f0,1 //V1 f1,2 //. . . fN−1,N //VN un m´odulo de persistencia y definamos fi,j :=    fj−1,j ◦. . . ◦fi,i+1, i + 1 < j, idVi, i =j. Entonces, existe un multiconjunto Mde intervalos de la forma [i, j), para 0≤i<j≤N, y de la forma [i, ∞), para 0≤i≤Ntal que, para cada 0≤i≤j≤N, la dimensi´on dim Imfi,j se puede calcular como la suma de la multiplicidad de cada intervalo en Mque contiene a [i, j]. La primera prueba del Teorema 1.2.4, debida a Carlsson y Zomorodian [23, §3], utiliza el teorema de estructura de los m´odulos graduados finitamente generados sobre un dominio de ideales principales, mientras que nosotros usamos una desigualdad de Frobenius sobre el rango de productos de matrices (v´ease §Section:P.H.) para todos los detalles). El Teorema 1.2.4 garantiza cierta facilidad en los c´alculos (como explicamos en §3.3) y permite obtener una imagen visual que captura la informaci´on de todos los grupos persistentes a la vez. Es m´as, resultados de estabilidad [28] nos dicen que en un cierto sentido, el n´umero de intervalos largos en el p-´esimo c´odigo de barras es robusto respecto a la introducci´on de ruido o de peque˜nas variaciones en la nube de puntos que estemos estudiando (o m´as generalmente, en K, provenga de donde provenga) y que este n´umero atesora informaci´on sobre rasgos topol´ogicos de nuestro objeto de estudio. Inspirados por esto, procedemos como sigue. El´ıjase una estructura de A∞-co´algebra buena {∆i n}nen la homolog´ıa de cada t´ermino Ki, que usaremos a lo largo del resto del resumen. Como para cada p≥0 y para cada 132 Resumen en Espa˜nol n≥1 queremos describir la evoluci´on del n´umero dim Ker ∆n|Hp(X)a lo largo de K, definimos lo que llamamos los grupos ∆n-persistentes (∆n-persistent groups) (∆n)i,j p(K) = Im fi,j p|∩j k=iKer(∆k n◦fi,k p),0≤i≤j≤N, y un multiconjunto de intervalos, que llamamos el p-´esimo ∆n-c´odigo de barras (pth ∆n-barcode), que cumplen lo siguiente: Corolario 3.6.5. Para cada p≥0yn≥1, el p-´esimo ∆n-c´odigo de barras de Kest´a bien definido y, para todo 0≤i≤j≤N, la dimensi´on del grupo ∆n-persistente (∆n)i,j p(K)es igual al n´umero de intervalos en el p-´esimo ∆n-c´odigo de barras de K(contados con multiplicidades) que continenen al intervalo [i, j]. En particular, dim Ker ∆i n|Hp(Ki)es igual al n´umero de intervalos en el el p-´esimo ∆n-c´odigo de barras de K(contados con multiplicidades) que continenen al valor i. Este es uno de los resultados m´as importantes de esta tesis. A continuaci´on mostramos el camino que seguimos para demostrarlo. En primer lugar, hay que tener en cuenta que eligiendo una base arbitraria de LN i=0 Hp(Ki), calcular los n´umeros dim Hi,j p(K) estudiando la evoluci´on a lo largo de Kde los elementos en esa base ser´ıa muy costoso, puesto que incolucrar´ıa el comprobar si las im´agenes por fi,j pde clases de homolog´ıa linealmente independientes son linealmente dependientes. El Teorema 1.2.4 se puede reescribir en t´erminos de la existencia de una base que permita tal c´alculo de una manera mucho m´as sencilla: Teorema 1.2.8. [23, §3] Para cada p≥0, existe una base Bde LN i=0 Hp(Ki) tal que, para todo 0≤i≤j≤N, la dimensi´on del grupo persistente Hi,j p(K) se puede calcular contando el n´umero de p-clases de homolog´ıa de la base que no se anulan en el rango correspondiente: dim Hi,j p(K) = #{β∈ B ∩Hp(Ki)|fi,jβ6= 0}. Resumen en Espa˜nol 133 En Homolog´ıa Persistente, podemos describir la igualdad anterior en t´erminos de clases que sobreviven a lo largo de un cierto rango, con la siguiente notaci´on cl´asica: Definici´on 1.2.1. Sean 0 ≤i≤j≤Nyp≥0. •Una clase α∈Hp(Ki)nace en Kisi α6= 0 y α /∈Im fi−1,i. •Una clase α∈Hp(Ki) que nace en Kise dice que est´a viva en Kj (donde i≤j) si fi,jα /∈Im fi−1,j.(4.0.1) Observemos que (4.0.1) es equivalente a decir que, para toda i < k ≤j, fi,kα /∈Im fi−1,k, que a su vez implica que fi,kα6= 0 para toda i < k ≤j. •Una clase α∈Hp(Ki) que nace en Kise dice que muere en Kj(donde i < j) si est´a viva en Kj−1pero no lo est´a en Kj,i.e., si fi,j−1α /∈Im fi−1,j−1yfi,jα∈Im fi−1,j. Esto implica que o bien fi,jα= 0 o bien existe alg´un β6= 0 ∈Hp(Ki−1) tal que fi−1,jβ=fi,jα, en cuyo caso decimos que αyβse han fundido en la misma clase, que la clase βes m´as antigua (porque naci´o en Kkpara alguna k≤ i−1, mientras que αnaci´o en Ki) y que βes, de las dos, la clase que representa a la clase en la que se han fundido (esto se conoce como la regla del m´as antiguo, o Elder Rule). De forma parecida, definimos los siguientes conceptos, que nos dotar´an de un vocabulario adecuado para expresar ciertos comportamientos y resultados con comodidad y con propiedad: 134 Resumen en Espa˜nol Definici´on 3.3.1. Sean 0 ≤i≤j≤N,p≥0 y n≥1. •Una clase α∈Hp(Ki)se ∆n-despierta en Kisi α6= 0, α ∈Ker ∆i nyα /∈Im fi−1,i |Ker ∆i−1 n. •Una clase α∈Hp(Ki) que se ∆n-despierta en Kidecimos que est´a ∆n-despierta en Kjsi para toda i < k ≤j, fi,kα∈Ker ∆k n y fi,kα /∈Im fi−1,k |Tk−1 l=i−1(fi−1,l)−1Ker ∆l n .(4.0.2) Notemos que (4.0.2) implica que fi,kα6= 0, para toda i<k≤j. •Una clase α∈Hp(Ki) que se ∆n-despierta en Kidecimos que se ∆nduerme en Kjsi est´a ∆n-despierto en Ki,Ki+1, . . . , Kj−1pero no lo est´a en Kj,i.e., si αest´a ∆n-despierta en Ki,Ki+1, ..., Kj−1y o bien fi,jα /∈Ker ∆j n, o bien fi,jα∈Im fi−1,j |Tj−1 l=i−1(fi−1,l)−1Ker ∆l n .(4.0.3) Observemos que (4.0.3) incluye la posibilidad fi,jα= 0. Hacemos notar que si una clase α∈Hp(Ki) nace en Kiy muere en Kl, entonces, si est´a ∆n-despierta en alg´un momento, deben existir jykcomo en i≤j < k ≤ltales que αse ∆n-despierta en Kjy se ∆n-duerme en Kk. Con esto empezamos a vislumbrar el porqu´e de la elecci´on de la terminolog´ıa dormido-despierto, que se termina de aclarar en §3.5. Adem´as, por una de las propiedades de las A∞-co´algebras buenas, tenemos lo siguiente: Observaci´on 3.3.2. Los conceptos de ∆1-despertarse y ∆1-dormirse coinciden con los de nacer y morir en persistencia cl´asica. Resumen en Espa˜nol 135 En A∞-persistencia, elegir una base arbitraria de LN i=0 Hp(Ki) y calcular los n´umeros dim(∆n)i,j p(K) estudiando la evoluci´on a lo largo de Kde los elementos de esa base ser´ıa a´un m´as costoso que en homolog´ıa persistente, puesto que involucrar´ıa comprobaciones m´as sutiles (v´ease §3.3 para m´as detalles). En esta direcci´on, empezamos por demostrar: Teorema 3.3.5. Fijemos enteros p≥0yn≥1. Si fi,i+1 p(Ker ∆i n)⊆ Ker ∆i+1 npara todo 0≤i<N, entonces existe una base Bde LN i=0 Hp(Ki) tal que, para cada 0≤i≤j≤N, la dimensi´on del grupo ∆n-persistente (∆n)i,j p(K)se puede calcular contando el n´umero de p-clases de homolog´ıa de la base se mantienen ∆n-despiertas a lo largo del correspondiente rango: dim(∆n)i,j p(K) = #{β∈ B ∩Hp(Ki)|fi,kβ∈Ker ∆k n−{0}para toda k=i, . . . , j}. M´as a´un, este n´umero es igual a #{β∈ B ∩Hp(Ki)|fi,jβ∈Ker ∆j− {0}}. Vale la pena se˜nalar que en efecto hay casos en los que se puede aplicar el Theorem 3.3.5: Teorema 3.4.1. Con coeficientes sobre los racionales Q, sea K0un CW complejo simplemente conexo y sea N≥0un entero. Si para todo 0< i ≤N, Kidenota un espacio simplemente conexo obtenido al adjuntarle a Ki−1una celda de modo que dim M p≥0 Hp(Ki) = dim M p≥0 Hp(Ki−1) + 1 (y por tanto cada adjunci´on produce nueva homolog´ıa), entonces existe una A∞-co´algebra buena e H∗(Ki),{∆i n}npara todo 0≤i≤N, y se tiene fi,i+1 Ker ∆i n⊆Ker ∆i+1 n, para cada n≥1y0≤i < N. 136 Resumen en Espa˜nol Yendo m´as all´a, si no nos restringimos a las hip´otesis del Teorema 3.3.5, hallamos un potencial comportamiento de intermitencia en las clases de homolog´ıa a lo largo de Kque describimos en §3.5. Esencialmente, el Teorema 3.5.1 muestra que las clases de homolog´ıa pueden ∆n-dormirse y ∆ndespertarse varias veces a lo largo de K(mientras est´en vivas). ´ Esta es la otra raz´on por la que elegimos la terminolog´ıa dormido-despierto. Probamos este resultado construyendo un ejemplo en el que tal comportamiento tiene lugar usando los racionales Qcomo coeficientes. De nuevo, recordamos que en el Ap´endice aparece todo los que necesitamos en lo referente a homotop´ıa racional. Para empezar, montamos una filtraci´on Kde CW complejos finitos K0 i0 ,→K1 i1 ,→K2 i2 ,→K3 como sigue: •K0= (S2 1∨S2 2∨S2 3∨S4)∪g1e6 1∪g2e6 2,donde S2 1,S2 2,S2 3denotan tres copiar distintas de S2y las (clases de homotop´ıa de las) funciones de adjunci´on de las 6-celdas e6 1, e6 2son los siguientes productos de Whitehead: g1= [idS4, idS2 1]+[idS2 1,[idS2 1,[idS2 1, idS2 2]]], g2= [idS4, idS2 2]. •K1=K0∪g3e4,donde g3= [idS2 1, idS2 2]. •K2=K1∪g4e6,donde g4= [idS4, idS2 1]−[idS2 2,[idS2 2,[idS2 2, idS2 3]]]. •K3=K2∪g5e4,donde g5= [idS2 2, idS2 3]. •Las aplicaciones i1, i2, i3son inclusiones. Entonces, demostramos Bibliography 143 [27] T. D. Cochran. Derivatives of Links: Milnor’s Concordance Invariants and Massey’s Products. Number 427 in Memoirs of the American Mathematical Society. American Mathematical Society, 1990. [28] D. Cohen-Steiner, H. Edelsbrunner, and J. Harer. Stability of persistence diagrams. Discrete Comput. Geom., 37:103–120, 2007. [29] M. Couprie and G. Bertrand. New characterizations of simple points, minimal nonsimple sets and p-simple points in 2D, 3D and 4D discrete spaces. In Proc. 14th IAPR Int. Conf. Discrete Geometry for Computer Imagery, pages 105–116, 2008. [30] M. Couprie and G. Bertrand. New characterizations of simple points in 2D, 3D and 4D discrete spaces. IEEE Trans. Pattern Analysis and Machine Intelligence, 31(4):637–648, 2009. [31] M. Couprie, F. N. Bezerra, and G. Bertrand. Topological operators for grayscale image processing. J. Electronic Imaging, 10(4):1003–1015, 2001. [32] M. D’Amico, P. Frosini, and C. Landi. Natural pseudo-distance and optimal matching between reduced size functions. Acta Appl. Math., 109:527–554, 2010. [33] V. de Silva and R. Ghrist. Coverage in sensor networks via persistent homology. Alg. & Geom. Top., 7:339–358, 2007. [34] H. Derksen and J. Weyman. Quiver representations. Not. Am. Math. Soc., 52(2):200–206, 2005. [35] N. Dupont. A counterexample to the Lemaire-Sigrist conjecture. Topology, 38(1):189–196, 1999. [36] W. G. Dwyer. Homology, Massey products and maps between groups. J. Pure Appl. Algebra, 6:177–190, 1975. [37] H. Edelsbrunner and J. Harer. Persistent homology – a survey. In Surveys on discrete and computational geometry, volume 453 of Contemp. Math., pages 257–282. Amer. Math. Soc., Providence, RI, 2008. [38] H. Edelsbrunner, G. Jab lo´nski, and M. Mrozek. The Persistent Homology of a Self-Map. Found. Comput. Math., 15(5):1213–1244, 2015. [39] H. Edelsbrunner, D. Letscher, and A. Zomorodian. Topological persistence and simplification. Discrete Comput. Geom., 28:511–533, 2002. [40] S. Eilenberg and J. A. Zilber. On products of complexes. American Journal of Mathematics, 75(1):200–204, 1953. 144 Bibliography [41] Y. F´elix, S. Halperin, and J. C. Thomas. Rational Homotopy Theory, volume 205 of Graduate Texts in Mathematics. Springer New York, 2001. [42] R. Fenn and D. Sjerve. Basic commutators and minimal Massey products. Canad. J. Math., 36:1119–1146, 1984. [43] M. Ferri, P. Frosini, A. Lovato, and C. Zambelli. Point selection: A new comparison scheme for size functions (with an application to monogram recognition). In Proc. ACCV ’98, volume 1, pages 329–337. Springer, 1998. [44] M. Ferri, S. Gallina, E. Porcellini, and M. Serena. On-line character and writer recognition by size functions and fuzzy logic. In Proc. ACCV ’95, volume 3, pages 622–626, 1995. [45] M. Ferri, S. Lombardini, and C. Pallotti. Leukocyte classification by size functions. In Proc. 2nd IEEE Workshop on Applications of Computer Vision, pages 223–229, 1994. [46] M. Ferri and I. Stanganelli. Size functions for the morphological analysis of melanocytic lesions. Int. J. Biomed. Imaging, 2010(Article ID 621357), 2010. [47] P. Frosini and C. Landi. Size theory as a topological tool for computer vision. Pattern Recogn. and Image Analysis, 9:596–603, 1999. [48] P. Gabriel. Unzerlegbare darstellungen i,. Manuscr. Math., 6:71–103, 1972. [49] E. Getzler and J. D. S. Jones. A∞-algebras and the cyclic bar complex. Illinois J. Math., 34(2):256–283, 1990. [50] R. Ghrist. Barcodes: the persistent topology of data. Bull. Amer. Math. Soc. (N.S.), 45(1):61–75, 2008. [51] W. H. Greub, S. Halperin, and R. Vanstone. Connections, Curvature and Cohomology VOL. III: Cohomology of principal bundles and homogeneous spaces, volume 47 of Monographs and textbooks in pure and applied mathematics. Academic Press, 1976. [52] V. K. A. M. Gugenheim, L. A. Lambe, and J. D. Stasheff. Perturbation theory in differential homological algebra. II. Illinois J. Math., 35(3):357–373, 1991. [53] M. Handouyahia, D. Ziou, and S. Wang. Sign language recognition using momentbased size functions. In Proc. Int. Conf. Vision Interface, pages 210–216. CRC Press, 1999. [54] A. Hatcher. Algebraic topology. Cambridge University Press, Cambridge, 2002. Bibliography 145 [55] A. R. Hebda-Bolduc. Persistent Cohomology Operations. PhD thesis, Duke University, 2011. [56] J. Huebschmann and T. Kadeishvili. Small models for chain algebras. Math. Z., 207(2):245–280, 1991. [57] M. J. Jim´enez and P. Real. Rectifications of A∞-algebras. Communications in Algebra, 35(9):2731–2743, 2007. [58] T. Kaczynski, K. Mischaikow, and M. Mrozek. Computational Homology. Number 157 in Applied Mathematical Sciences. Springer, 2004. [59] T. Kaczynski and M. Mrozek. The cubical cohomology ring: An algorithmic approach. Foundations of Computational Mathematics, 13(5):789–818, 2013. [60] T. Kadeishvili. On the homology theory of fibrations. Russian Mathematical Surveys, 35(3):231–238, 1980. Previously published in Russian in Uspekhi Mat. Nauk 35(3):183–188, 1980. [61] T. Kadeishvili and P. Real. Free resolutions for differential modules over differential algebras. J. Math. Sci. (N. Y.), 152(3):307–322, 2008. Topology and its applications. [62] D. Kelly, J. McDonald, T. Lysaght, and Ch. Markham. Analysis of sign language gestures using size functions and principal component analysis. In Proc. IMVIP2008, pages 31–36, 2008. [63] M. Kontsevich. Homological algebra of mirror symmetry. In Proceedings of the International Congress of Mathematicians, Vol. 1, 2 (Z¨urich, 1994), pages 120–139. Birkh¨auser, Basel, 1995. [64] M. Kontsevich and Y. Soibelman. Deformations of algebras over operads and Deligne’s conjecture. In G. Dito and D. Sternheimer, editors, Conf´erence Mosh´e Flato 1999: Quantization, Deformations, and Symmetries, volume 1, pages 255– 307. Springer, 2000. [65] V. A. Kovalevsky. Finite topology as applied to image analysis. Computer Vision, Graphics, and Image Processing, 46(2):141–161, 1989. [66] D. Kraines. Massey higher products. Trans. Amer. Math. Soc., 124:431–449, 1966. [67] D. Kraines and C. Schochet. Differentials in the Eilenberg-Moore spectral sequence. Journal of Pure and Applied Algebra, 2:131–148, 1972. [68] J.-L. Loday and B. Vallette. Algebraic operads. Number 346 in Grundlehren der mathematischen Wissenschaften. Springer, 2012. 146 Bibliography [69] D.-M. Lu, J. H. Palmieri, Q.-S. Wu, and J. J Zhang. A∞structure on Ext-algebras. Journal of Pure and Applied Algebra, 213:2017–2037, 2009. [70] W. S. Massey. Some higher order cohomology operations. In International Symposium on Algebraic Topology, pages 145–154. Universidad Nacional Aut´onoma de M´exico and UNESCO, 1958. [71] W. S. Massey. Higher order linking numbers. Journal of Knot Theory and Its Ramifications, 7:393–414, 1998. Originally published in Conference on Algebraic Topology, ed. Victor Gugenheim; a collection of papers presented at the University of Illinois at Chicago Circle, June 17–June 28, 1968. [72] J. P. May. The Geometry of Iterated Loop Spaces, volume 271 of Lecture Notes in Mathematics. Springer-Verlag, Berlin-Heidelberg-New York, 1972. [73] J. McCleary, editor. Higher homotopy structures in topology and mathematical physics, volume 227 of Contemporary Mathematics. American Mathematical Society, Providence, RI, 1999. [74] J. McCleary. A User’s Guide to Spectral Sequences. Cambridge University Press, 2000. [75] S. A. Merkulov. Strong homotopy algebras of a K¨ahler manifold. International Mathematics Research Notices, 3:153–164, 1999. [76] A. Micheletti and G. Landini. Size functions applied to the statistical shape analysis and classification of tumor cells. In Progress in Industrial Mathematics at ECMI 2006, volume 12 of Mathematics in Industry, pages 538–542, 2008. [77] A. Micheletti, F. Terragni, and M. Vasconi. Statistical aspects of size functions for the description of random shapes: Applications to problems of lithography in microelectronics. In Progress in Industrial Mathematics at ECMI 2006, volume 12 of Mathematics in Industry, pages 123–134, 2008. [78] J. W. Milnor. The geometric realization of a semi-simplicial complex. Ann. of Math., 65:357–362, 1957. [79] H. Molina-Abril and P. Real. Advanced homology computation of digital volumes via cell complexes. In Structural, Syntactic, and Statistical Pattern Recogn., volume 5342 of Lecture Notes in Computer Science, pages 361–371. Springer, 2008. [80] H. Molina-Abril and P. Real. Cell AT-models for digital volumes. In GraphBased Representations in Pattern Recogn. (7th IAPR-TC-15 International Workshop, GbRPR 2009), volume 5534 of Lecture Notes in Computer Science, pages 314–323. Springer, 2009. Bibliography 147 [81] J. R. Munkres. Elements of Algebraic Topology. Perseus Books, 1984. [82] P. Niyogi, S. Smale, and S. Weinberger. Finding the homology of submanifolds with high confidence from random samples. Discrete Comput. Geom., 39:419–441, 2008. [83] K. E. Orr. Link concordance invariants and Massey products. Topology, 30:699–710, 1991. [84] R. Porter. Milnor’s µ-invariants and Massey products. Trans. Amer. Math. Soc., 257:39–71, 1980. [85] V. V. Prasolov. Elements of Homology Theory, volume 81 of Graduate Studies in Mathematics. American Mathematical Society, 2007. [86] A. Prout´e. Alg`ebres differentielles fortement homotopiquement associatives. PhD thesis, Universit´e Paris VII, 1984. [87] D. Quillen. Rational homotopy theory. Ann. of Math. (2), 90:205–295, 1969. [88] V. Robins. Towards computing homology from finite approximations. In Proceedings of the 14th Summer Conference on General Topology and its Applications (Brookville, NY, 1999), volume 24, pages 503–532 (2001), 1999. [89] V. Robins, P. J. Wood, and A. P. Sheppard. Theory and algorithms for constructing discrete Morse complexes from grayscale digital images. IEEE Trans. Pattern Analysis and Machine Intelligence, 33(8):1646–1658, 2011. [90] D. Rolfsen. Knots and Links. Number 7 in Mathematics Lecture Series. Publish or Perish, 1976. [91] V. Smirnov. Homology of fiber spaces. Russian Math. Surveys, 35(3):294–298, 1980. [92] E. H. Spanier. Algebraic Topology. Springer-Verlag, New York, 1966. [93] J. Stallings. Homology and central series of groups. J. Algebra, 2:170–181, 1965. [94] J. D. Stasheff. Homotopy associativity of H-spaces. I, II. Trans. Amer. Math. Soc., 108:275–312, 1963. [95] J. D. Stasheff. Differential graded lie algebras, quasi-hopf algebras and higher homotopy algebras. In PetrP. Kulish, editor, Quantum Groups, volume 1510 of Lecture Notes in Mathematics, pages 120–137. Springer Berlin Heidelberg, 1992. [96] D. Stein. Massey products in the cohomology of groups with applications to link theory. Trans. Amer. Math. Soc., 318:301–325, 1990. [97] D. Tanr´e. Homotopie rationnelle: mod`eles de Chen, Quillen, Sullivan, volume 1025 of Lecture Notes in Mathematics. Springer-Verlag, Berlin, 1983. 148 Bibliography [98] V. G. Turaev. The Milnor invariants and Massey products. Studies in Topology, II. Zap. Nauˇcn. (LOMI), 66:189–203, 1976. (In Russian) English translation in J. Soviet Math., 12(1): 128–137, 1979. [99] H. Uehara and W. S. Massey. The Jacobi identity for Whitehead products. In Algebraic geometry and topology, a symposium in honor of S. Lefschetz, pages 361– 377, 1957. [100] C. Uras and A. Verri. On the recognition of the alphabet of the sign language through size functions. In Proc. XII Int. Conf. IAPR, pages 334–338, 1994. [101] M. Vejdemo-Johansson. Blackbox computation of A∞-algebras. Georgian Math. J., 17(2):391–404, 2010. [102] M. Vejdemo-Johansson. Sketches of a platypus: a survey of persistent homology and its algebraic foundations. In Algebraic topology: applications and new directions, volume 620 of Contemp. Math., pages 295–319. Amer. Math. Soc., Providence, RI, 2014. [103] A. Zomorodian. Computing and Comprehending Topology: Persistence and Hierarchical Morse Complexes. PhD thesis, University of Illinois at Urbana-Champaign, 2001.