Cellular approximations to the diagonal map

Alzobydi, Khaled; Ellis, Graham

doi:10.1090/mcom/3981

Cellular approximations to the diagonal map
HTML articles powered by AMS MathViewer

by Khaled Alzobydi and Graham Ellis;

Math. Comp. 94 (2025), 953-1002

DOI: https://doi.org/10.1090/mcom/3981

Published electronically: May 28, 2024

HTML | PDF | Request permission

Abstract:

We describe an elementary algorithm for recursively constructing diagonal approximations on those finite regular CW-complexes for which the closure of each cell can be explicitly collapsed to a point. The algorithm is based on the standard proof of the acyclic carrier theorem, made constructive through the use of explicit contracting homotopies. It can be used as a theoretical tool for constructing diagonal approximations on families of polytopes in situations where the diagonals are required to satisfy certain coherence conditions. We compare its output to existing diagonal approximations for the families of simplices, cubes, associahedra and permutahedra. The algorithm yields a new explanation of a magical formula for the associahedron derived by Markl and Shnider [Trans. Amer. Math. Soc. 358 (2006), pp. 2353–2372] and Masuda, Thomas, Tonks, and Vallette [J. Éc. polytech. Math. 8 (2021), pp. 121–146] and Theorem 4.1 provides a magical formula for other polytopes. We also describe a computer implementation of the algorithm and illustrate it on a range of practical examples including the computation of cohomology rings for some low-dimensional manifolds. To achieve some of these examples the paper includes two approaches to generating a regular CW-complex structure on closed compact $3$-manifolds, one using an implementation of Dehn surgery on links and the other using an implementation of pairwise identifications of faces in a tessellated boundary of the $3$-ball. The latter is illustrated in Proposition 8.1 with a topological classification of all closed orientable $3$-manifolds arising from pairwise identifications of faces of the cube.

References

Kerstin Aaslepp, Michael Drawe, Claude Hayat-Legrand, Christian A. Sczesny, and Heiner Zieschang, On the cohomology of Seifert and graph manifolds, Proceedings of the Pacific Institute for the Mathematical Sciences Workshop “Invariants of Three-Manifolds” (Calgary, AB, 1999), 2003, pp. 3–32. MR 1953318, DOI 10.1016/S0166-8641(02)00040-8
D. Al-Baidli, Computation of cohomology operations for finite groups, Ph. D. Thesis, University of Galway, 2018.
Nisreen Alokbi and Graham Ellis, Distributed computation of low-dimensional cup products, Homology Homotopy Appl. 20 (2018), no. 2, 41–59. MR 3795420, DOI 10.4310/HHA.2018.v20.n2.a3
Daniel Altschüler and Antoine Coste, Invariants of three-manifolds from finite group cohomology, J. Geom. Phys. 11 (1993), no. 1-4, 191–203. Infinite-dimensional geometry in physics (Karpacz, 1992). MR 1230426, DOI 10.1016/0393-0440(93)90053-H
Emil Artin, Zur Isotopie zweidimensionaler Flächen im $R_4$, Abh. Math. Sem. Univ. Hamburg 4 (1925), no. 1, 174–177 (German). MR 3069446, DOI 10.1007/BF02950724
Manifold Atlas. Linking form, The Manifold Atlas Project, 2013, http://www.map.mpim-bonn.mpg.de/Linking_form.
Aubrey HB, Persistent Cohomology Operations, ProQuest LLC, Ann Arbor, MI, 2011. Thesis (Ph.D.)–Duke University. MR 2873406
Anne Bauval and Claude Hayat, L’anneau de cohomologie des variétés de Seifert, C. R. Math. Acad. Sci. Paris 351 (2013), no. 3-4, 81–85 (French, with English and French summaries). MR 3037991, DOI 10.1016/j.crma.2013.02.008
Anne Bauval and Claude Hayat, L’anneau de cohomologie des variétés de Seifert non-orientables, Osaka J. Math. 54 (2017), no. 1, 157–195 (French, with English and French summaries). MR 3619753
Francisco Belchí and Anastasios Stefanou, $A_\infty$ persistent homology estimates detailed topology from pointcloud datasets, Discrete Comput. Geom. 68 (2022), no. 1, 274–297. MR 4430289, DOI 10.1007/s00454-021-00319-y
Bruno Benedetti and Frank H. Lutz, Knots in collapsible and non-collapsible balls, Electron. J. Combin. 20 (2013), no. 3, Paper 31, 29. MR 3104529, DOI 10.37236/3319
R. H. Bing, Some aspects of the topology of $3$-manifolds related to the Poincaré conjecture, Lectures on Modern Mathematics, Vol. II, Wiley, New York-London-Sydney, 1964, pp. 93–128. MR 172254
Anders Björner, Orderings of Coxeter groups, Combinatorics and algebra (Boulder, Colo., 1983) Contemp. Math., vol. 34, Amer. Math. Soc., Providence, RI, 1984, pp. 175–195. MR 777701, DOI 10.1090/conm/034/777701
Adam Bliss and Francis Edward Su, Lower bounds for simplicial covers and triangulations of cubes, Discrete Comput. Geom. 33 (2005), no. 4, 669–686. MR 2132296, DOI 10.1007/s00454-004-1128-0
Wieb Bosma, John Cannon, and Catherine Playoust, The Magma algebra system. I. The user language, J. Symbolic Comput. 24 (1997), no. 3-4, 235–265. Computational algebra and number theory (London, 1993). MR 1484478, DOI 10.1006/jsco.1996.0125
A. Bostan, F. Chyzak, and V. Pilaud, Refined product formulas for Tamari intervals, 2023, arXiv:2212.01633.
J. Bryden, Cohomology rings of oriented Seifert manifolds with mod $p^s$ coefficients, Advances in topological quantum field theory, NATO Sci. Ser. II Math. Phys. Chem., vol. 179, Kluwer Acad. Publ., Dordrecht, 2004, pp. 317–326. MR 2147427, DOI 10.1007/978-1-4020-2772-7_{1}4
J. Bryden, C. Hayat-Legrand, H. Zieschang, and P. Zvengrowski, The cohomology ring of a class of Seifert manifolds, Topology Appl. 105 (2000), no. 2, 123–156. MR 1761426, DOI 10.1016/S0166-8641(99)00062-0
J. Bryden, T. Lawson, B. Pigott, and P. Zvengrowski, The integral homology of orientable Seifert manifolds, Proceedings of the Pacific Institute for the Mathematical Sciences Workshop “Invariants of Three-Manifolds” (Calgary, AB, 1999), 2003, pp. 259–275. MR 1953329, DOI 10.1016/S0166-8641(02)00062-7
J. Bryden and P. Zvengrowski, The cohomology algebras of orientable Seifert manifolds and applications to Lusternik-Schnirelmann category, Homotopy and geometry (Warsaw, 1997) Banach Center Publ., vol. 45, Polish Acad. Sci. Inst. Math., Warsaw, 1998, pp. 25–39. MR 1679847
J. Bryden and P. Zvengrowski, The cohomology ring of the orientable Seifert manifolds. II, Proceedings of the Pacific Institute for the Mathematical Sciences Workshop “Invariants of Three-Manifolds” (Calgary, AB, 1999), 2003, pp. 213–257. MR 1953328, DOI 10.1016/S0166-8641(02)00061-5
John Bryden, Claude Hayat-Legrand, Heiner Zieschang, and Peter Zvengrowski, L’anneau de cohomologie d’une variété de Seifert, C. R. Acad. Sci. Paris Sér. I Math. 324 (1997), no. 3, 323–326 (French, with English and French summaries). MR 1438408, DOI 10.1016/S0764-4442(99)80369-3
Jon F. Carlson, Lisa Townsley, Luis Valeri-Elizondo, and Mucheng Zhang, Cohomology rings of finite groups, Algebra and Applications, vol. 3, Kluwer Academic Publishers, Dordrecht, 2003. With an appendix: Calculations of cohomology rings of groups of order dividing 64 by Carlson, Valeri-Elizondo and Zhang. MR 2028960, DOI 10.1007/978-94-017-0215-7
Cesar Ceballos, Francisco Santos, and Günter M. Ziegler, Many non-equivalent realizations of the associahedron, Combinatorica 35 (2015), no. 5, 513–551. MR 3437894, DOI 10.1007/s00493-014-2959-9
F. Chapoton, Sur le nombre d’intervalles dans les treillis de Tamari, Sém. Lothar. Combin. 55 (2005/07), Art. B55f, 18 (French, with English and French summaries). MR 2264942
Rocco Chirivì and Mauro Spreafico, Space forms and group resolutions: the tetrahedral family, J. Algebra 510 (2018), 52–97. MR 3828780, DOI 10.1016/j.jalgebra.2018.06.004
Marco Contessoto, Facundo Mémoli, Anastasios Stefanou, and Ling Zhou, Persistent cup-length, 38th International Symposium on Computational Geometry, LIPIcs. Leibniz Int. Proc. Inform., vol. 224, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2022, pp. Art. No. 31, 17. MR 4470910, DOI 10.4230/lipics.socg.2022.31
Michael W. Davis, The geometry and topology of Coxeter groups, London Mathematical Society Monographs Series, vol. 32, Princeton University Press, Princeton, NJ, 2008. MR 2360474
T. K. Dey and A. Rathod, Cup product persistence and its efficient computation, 2023, arXiv:2212.01633.
Robbert Dijkgraaf and Edward Witten, Topological gauge theories and group cohomology, Comm. Math. Phys. 129 (1990), no. 2, 393–429. MR 1048699, DOI 10.1007/BF02096988
Herbert Edelsbrunner and John L. Harer, Computational topology, American Mathematical Society, Providence, RI, 2010. An introduction. MR 2572029, DOI 10.1090/mbk/069
F. Effenberger and J. Spreer, simpcomp, a gap toolbox for simplicial complexes, version 2.1.14, March 2022, https://simpcomp-team.github.io/simpcomp. Refereed GAP package.
Samuel Eilenberg and J. A. Zilber, On products of complexes, Amer. J. Math. 75 (1953), 200–204. MR 52767, DOI 10.2307/2372629
G. Ellis, HAP – homological algebra programming, 2024, https://gap-packages.github.io/hap/.
G. Ellis, Appendix to cellular approximations to the diagonal map, March 2024, https://github.com/gap-packages/hap/blob/gh-pages/tutorial/appendix.g.
Graham Ellis, An invitation to computational homotopy, Oxford University Press, Oxford, 2019. MR 3971587, DOI 10.1093/oso/9780198832973.001.0001
Graham Ellis and Kelvin Killeen, Cohomology with local coefficients and knotted manifolds, J. Symbolic Comput. 107 (2021), 299–321. MR 4255482, DOI 10.1016/j.jsc.2021.04.004
Brent Everitt, 3-manifolds from Platonic solids, Topology Appl. 138 (2004), no. 1-3, 253–263. MR 2035484, DOI 10.1016/j.topol.2003.08.025
L. L. Fêmina, A. P. T. Galves, O. Manzoli Neto, and M. Spreafico, Cellular decomposition and free resolution for split metacyclic spherical space forms, Homology Homotopy Appl. 15 (2013), no. 1, 253–278. MR 3079207, DOI 10.4310/HHA.2013.v15.n1.a13
K. Fleming, A cellular diagonal approximation on the sequence of associahedra, Ph. D. Thesis, University of Leicester, 2020.
Robin Forman, Morse theory for cell complexes, Adv. Math. 134 (1998), no. 1, 90–145. MR 1612391, DOI 10.1006/aima.1997.1650
Daniel S. Freed and Robert E. Gompf, Computer calculation of Witten’s $3$-manifold invariant, Comm. Math. Phys. 141 (1991), no. 1, 79–117. MR 1133261, DOI 10.1007/BF02100006
The GAP Group, GAP – groups, algorithms, and programming, version 4.12.0, 2022, http://www.gap-system.org.
Daciberg Lima Gonçalves and Sérgio Tadao Martins, Diagonal approximation and the cohomology ring of the fundamental groups of surfaces, Eur. J. Math. 1 (2015), no. 1, 122–137. MR 3386228, DOI 10.1007/s40879-014-0031-3
R. Gonzalez-Diaz, M. J. Jimenez, and B. Medrano, Cohomology ring of 3D cubical complexes, Lecture Notes in Computer Science, vol. 5852, Springer, 2009, pp. 139–150
Rocio Gonzalez-Diaz, Javier Lamar, and Ronald Umble, Cup products on polyhedral approximations of 3D digital images, Combinatorial image analysis, Lecture Notes in Comput. Sci., vol. 6636, Springer, Heidelberg, 2011, pp. 107–119. MR 2813677, DOI 10.1007/978-3-642-21073-0_{1}2
Rocio Gonzalez-Diaz, Javier Lamar, and Ronald Umble, Computing cup products in $\Bbb {Z}_2$-cohomology of 3D polyhedral complexes, Found. Comput. Math. 14 (2014), no. 4, 721–744. MR 3230013, DOI 10.1007/s10208-014-9193-0
R. González-Díaz and P. Real, Computation of cohomology operations of finite simplicial complexes, Homology Homotopy Appl. 5 (2003), no. 2, 83–93. Algebraic topological methods in computer science (Stanford, CA, 2001). MR 1994941, DOI 10.4310/HHA.2003.v5.n2.a4
Rocío González-Díaz and Pedro Real, On the cohomology of 3D digital images, Discrete Appl. Math. 147 (2005), no. 2-3, 245–263. MR 2127077, DOI 10.1016/j.dam.2004.09.014
Jacob E. Goodman, Joseph O’Rourke, and Csaba D. Tóth (eds.), Handbook of discrete and computational geometry, Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL, 2018. Third edition of [ MR1730156]. MR 3793131
David J. Green and Simon A. King, The computation of the cohomology rings of all groups of order 128, J. Algebra 325 (2011), 352–363. MR 2745544, DOI 10.1016/j.jalgebra.2010.08.016
Pierre Guillot, The computation of Stiefel-Whitney classes, Ann. Inst. Fourier (Grenoble) 60 (2010), no. 2, 565–606 (English, with English and French summaries). MR 2667787, DOI 10.5802/aif.2533
Allen Hatcher, Algebraic topology, Cambridge University Press, Cambridge, 2002. MR 1867354
Claude Hayat-Legrand and Heiner Zieschang, On the cup product on Seifert manifolds, Mat. Contemp. 13 (1997), 159–180. 10th Brazilian Topology Meeting (São Carlos, 1996). MR 1630635
James E. Humphreys, Reflection groups and Coxeter groups, Cambridge Studies in Advanced Mathematics, vol. 29, Cambridge University Press, Cambridge, 1990. MR 1066460, DOI 10.1017/CBO9780511623646
OEIS Foundation Inc. The On-line Encyclopedia of Integer Sequences, 2024, https://oeis.org.
Tomasz Kaczynski, Konstantin Mischaikow, and Marian Mrozek, Computational homology, Applied Mathematical Sciences, vol. 157, Springer-Verlag, New York, 2004. MR 2028588, DOI 10.1007/b97315
Tomasz Kaczynski and Marian Mrozek, The cubical cohomology ring: an algorithmic approach, Found. Comput. Math. 13 (2013), no. 5, 789–818. MR 3105945, DOI 10.1007/s10208-012-9138-4
T. Kaczyński, M. Mrozek, and M. Ślusarek, Homology computation by reduction of chain complexes, Comput. Math. Appl. 35 (1998), no. 4, 59–70. MR 1604791, DOI 10.1016/S0898-1221(97)00289-7
T. Kaczynski, P. Dlotko, and M. Mrozek, Computing the cubical cohomology ring, Image-A Appl. Math. Image Eng. 1 (2010), no. 3, 137–142
Marek Krčál and PawełPilarczyk, Computation of cubical Steenrod squares, Computational topology in image context, Lecture Notes in Comput. Sci., vol. 9667, Springer, [Cham], 2016, pp. 140–151. MR 3533883, DOI 10.1007/978-3-319-39441-1_{1}3
Guillaume Laplante-Anfossi, The diagonal of the operahedra, Adv. Math. 405 (2022), Paper No. 108494, 50. MR 4437611, DOI 10.1016/j.aim.2022.108494
R. Lipshitz, P. Ozsváth, and D. Thurston, Diagonals and A-infinity tensor products, 2023, arXiv:2212.01633.
Jean-Louis Loday, The diagonal of the Stasheff polytope, Higher structures in geometry and physics, Progr. Math., vol. 287, Birkhäuser/Springer, New York, 2011, pp. 269–292. MR 2762549, DOI 10.1007/978-0-8176-4735-3_{1}3
Umberto Lupo, Anibal M. Medina-Mardones, and Guillaume Tauzin, Persistence Steenrod modules, J. Appl. Comput. Topol. 6 (2022), no. 4, 475–502. MR 4496688, DOI 10.1007/s41468-022-00093-7
Martin Markl and Steve Shnider, Associahedra, cellular $W$-construction and products of $A_\infty$-algebras, Trans. Amer. Math. Soc. 358 (2006), no. 6, 2353–2372. MR 2204035, DOI 10.1090/S0002-9947-05-04006-7
Sérgio Tadao Martins, Diagonal approximation and the cohomology ring of torus fiber bundles, Internat. J. Algebra Comput. 25 (2015), no. 3, 493–530. MR 3334647, DOI 10.1142/S0218196715500071
Naruki Masuda, Hugh Thomas, Andy Tonks, and Bruno Vallette, The diagonal of the associahedra, J. Éc. polytech. Math. 8 (2021), 121–146 (English, with English and French summaries). MR 4191110, DOI 10.5802/jep.142
Anibal M. Medina-Mardones, New formulas for cup-$i$ products and fast computation of Steenrod squares, Comput. Geom. 109 (2023), Paper No. 101921, 16. MR 4473678, DOI 10.1016/j.comgeo.2022.101921
Robert E. Mosher and Martin C. Tangora, Cohomology operations and applications in homotopy theory, Harper & Row, Publishers, New York-London, 1968. MR 226634
Facundo Mémoli, Anastasios Stefanou, and Ling Zhou, Persistent cup product structures and related invariants, J. Appl. Comput. Topol. 8 (2024), no. 1, 93–148. MR 4707458, DOI 10.1007/s41468-023-00138-5
Takefumi Nosaka, Cellular chain complexes of universal covers of some 3-manifolds, J. Math. Sci. Univ. Tokyo 29 (2022), no. 1, 89–113. MR 4414248
PawełPilarczyk and Pedro Real, Computation of cubical homology, cohomology, and (co)homological operations via chain contraction, Adv. Comput. Math. 41 (2015), no. 1, 253–275. MR 3311480, DOI 10.1007/s10444-014-9356-1
H. Poincaré, Analysis situs, J. Éc. polytech. Math. 1 (1895), no. 2, 1–123
L. Préville-Ratelle and X. Viennot, An extension of Tamari lattices, Discrete Math. Theor., DMTCS Proceedings, 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015), 2015, DOI 10.46298/dmtcs.2535.
David J. Rusin, The cohomology of the groups of order $32$, Math. Comp. 53 (1989), no. 187, 359–385. MR 968153, DOI 10.1090/S0025-5718-1989-0968153-8
Samson Saneblidze and Ronald Umble, Diagonals on the permutahedra, multiplihedra and associahedra, Homology Homotopy Appl. 6 (2004), no. 1, 363–411. MR 2118493, DOI 10.4310/HHA.2004.v6.n1.a20
Samson Saneblidze and Ronald Umble, Diagonals on the permutahedra, multiplihedra and associahedra, Homology Homotopy Appl. 6 (2004), no. 1, 363–411. MR 2118493, DOI 10.4310/HHA.2004.v6.n1.a20
Jean-Pierre Serre, Homologie singulière des espaces fibrés. Applications, Ann. of Math. (2) 54 (1951), 425–505 (French). MR 45386, DOI 10.2307/1969485
A. R. Shastri, J. G. Williams, and P. Zvengrowski, Kinks in general relativity, Internat. J. Theoret. Phys. 19 (1980), no. 1, 1–23. MR 573655, DOI 10.1007/BF00670210
Jonathan Spreer and Wolfgang Kühnel, Combinatorial properties of the $K3$ surface: simplicial blowups and slicings, Exp. Math. 20 (2011), no. 2, 201–216. MR 2821391, DOI 10.1080/10586458.2011.564546
N. E. Steenrod, Cohomology operations, Annals of Mathematics Studies, No. 50, Princeton University Press, Princeton, NJ, 1962. Lectures by N. E. Steenrod written and revised by D. B. A. Epstein. MR 145525
W. A. Stein, et al., Sage mathematics software (version 5.10), The Sage Development Team, 2013, http://www.sagemath.org.
Alexander I. Suciu and He Wang, Cup products, lower central series, and holonomy Lie algebras, J. Pure Appl. Algebra 223 (2019), no. 8, 3359–3385. MR 3926216, DOI 10.1016/j.jpaa.2018.11.006
D. B. Sumner, Orientable manifolds constructed from a solid cube, Trans. Roy. Soc. South Africa 28 (1940), 183–197. MR 1905, DOI 10.1080/00359194009520012
Dov Tamari, The algebra of bracketings and their enumeration, Nieuw Arch. Wisk. (3) 10 (1962), 131–146. MR 146227
A. Tenie, Strongly isospectral hyperbolic 3-manifolds with nonisomorphic rational cohomology rings, 2021, arXiv:2111.11454.
Satoshi Tomoda and Peter Zvengrowski, Remarks on the cohomology of finite fundamental groups of 3-manifolds, The Zieschang Gedenkschrift, Geom. Topol. Monogr., vol. 14, Geom. Topol. Publ., Coventry, 2008, pp. 519–556. MR 2484716, DOI 10.2140/gtm.2008.14.519
M. Vejdemo-Johansson, Enumerating the Saneblidze-Umble diagonal in Haskell, ACM Commun. Comput. Algebra 42 (2008), no. 1–2, 235–265
K. Volkert, Poincaré’s cube manifolds, Bull. Manifold Atlas (2013)
Michihisa Wakui, On Dijkgraaf-Witten invariant for $3$-manifolds, Osaka J. Math. 29 (1992), no. 4, 675–696. MR 1192735
S. J. Weaver, Computing the Saneblidze-Umble diagonal on permutahedra, Undergraduate Thesis, Millersville University, 2005.
J. H. C. Whitehead, On incidence matrices, nuclei and homotopy types, Ann. of Math. (2) 42 (1941), 1197–1239. MR 5352, DOI 10.2307/1970465