About the Kannan-Bachem algorithm.
Abstract:The Smith reduction is a basic tool when analyzing integer matrices up to equivalence, and the Kannan-Bachem (KB) algorithm is the first polynomial algorithm computing such a reduction. Using this algorithm in complicated situations where the rank of the studied matrix is not maximal revealed an unexpected obstacle in the algorithm. This difficulty is described, analyzed, a simple solution is given to overcome it, finally leading to a general organization of the KB algorithm, simpler than the original one, effcient and having a general scope. An equivalent algorithm is used by the Magma program, without any detailed explanation, without any reference. The present text could so be useful.
The Eilenberg-Zilber Theorem
via Discrete Vector Fields.
Abstract: The Eilenberg-Zilber (EZ) Theorem is basic in Algebraic Topology. It connects the chain complex \(C_\ast(A \times B)\) of the product of two simplicial sets to the tensor product \(C_\ast (A) \otimes C_\ast (B)\), allowing one to compute \(H_\ast(A \times B)\) from \(H_\ast(A)\) and \(H_\ast(B)\). Initially proved in 1953, it is stated and used in almost every elementary textbook of Algebraic Topology. Sixty-five years after the initial EZ paper, we present this result via a totally new proof, based on the relatively recent tool called Discrete Vector Field (DVF, Robin Forman, 1998). The various available EZ proofs are not so trivial; the present proof on the contrary is intuitive and gives more information. The key point is the notion of s-path, a 2-dimensional description of every simplex of the standard simplicial decomposition of \(\Delta^p \times \Delta^q\), \(p\) and \(q\) arbitrary, which allows us to use the same DVF for the homotopical and homological EZ theorems. The right notion of morphism between cellular chain complexes provided with discrete vector fields is given; its definition is really amazing and is here an essential tool. Besides a new understanding of the EZ theorem, we obtain much better algorithms for the machine implementation of the EZ theorem, automatically avoiding the countless degenerate simplices produced by the Rubio-Morace formula for the EZ-homotopy. Other striking applications will be the subject of other papers.
An implementation of effective homotopy of
fibrations.
Abstract: In this paper, we present a new module for the Kenzo system which makes it possible to compute the effective homotopy of the total space of a fibration, using the well-known long exact sequence of homotopy of a fibration defined by Jean-Pierre Serre. The programs are written in Common Lisp and require the implementation of new classes and functions corresponding to the definitions of setoid group (SG) and effective setoid group (ESG). Moreover, we have included a new module for working with finitely generated abelian groups, choosing the representation of a free presentation by means of a matrix in canonical form. These tools are then used to implement the long exact homotopy sequence of a fibration. We illustrate with examples some applications of our results. Published in Journal of Symbolic Computation, August 2018 (DOI).
The Homological Hexagonal Lemma.
Abstract: We propose in this article a global understanding of, on the one hand, the Homological Perturbation Theorem (HPT) and, on the other hand, of Robin Forman's theorems about the Discrete Vector Fields. Forman's theorems become a simple and clear consequence of the HPT. Above both subjects the Homological Hexagonal Lemma, quite elementary. Published in Georgian Mathematical Journal, September 2018 (DOI).
Infini et effectivité, le point de vue fonctionnel
(in French).
Infinity and Effectiveness from a Functional Point
of View
(English translation due to Gerd Heber).
The pdf of a didactic paper explaining how functional programming can be convenient and powerful. A lovely algorithm computes the chromatic number of a graph, using polynomials describing an infinity of facts. Computing the chromatic number of a graph is known of type NP. Can be considered also as a particular sort of generating function, the power of which is well known.
Published in the French journal Images des Mathématiques, 1990, vol.76, pp.71-81.
It is a didactic paper: the "functional objects" defined and used here are simple polynomials of Z[X], which do not need in fact functional objects in the environment, simple lists are enough. On the contrary, in Effective Homology, arbitrary complicated functional objects have to be dynamically defined and constructed, and the standard funarg problem requires a programming language able to construct closures.
Functional Programming is Free.
Abstract:A paper has recently been published in SIAM JC. This paper is faulty: 1) The standard requirements about the definition of an algorithm are not respected, 2) The main point in the complexity study, namely the functional programming component, is absent. The Editorial Board of the SIAM JC had been warned a confirmed publication would be openly commented, it is the role of this text.
A Bousfield-Kan algorithm for computing homotopy groups of spaces.
The first try to make constructive the Bousfield-Kan spectral sequence. This spectral sequence is the combinatorial basic tool underlying the Adams spectral sequence. Published in Foundations of Computational Mathematics, May 2016.
A combinatorial tool for computing the effective homotopy of iterated loop spaces.
An amusing discrete vector field is used to prove a result which is obvious in ordinary topology, but surprisingly difficult in simplicial topology. Then applied to basic problems of effective homotopy. Discrete and Computational Geometry, 2015, vol.53, pp.1-15.
Computing all maps into a sphere.
"Long version" of the SODA paper below. Accepted at JACM.
Packaging in Common Lisp, a tutorial.
Just for info, not intended to be published.
Gerd Heber (thanks!) translated this text into a Jupyter page allowing a GitHub user to interactively follow the corresponding Lisp session and to freely do arbitrary extra tests.
Polynomial-time homology for simplicial Eilenberg-MacLane spaces.
Accepted in Foundations of Computational Mathematics.
A curious and amazing complexity problem, for a terribly elementary algorithm, but with exponential complexity in his ordinary form.
Programming before Theorizing, a case study.
Accepted for the ISSAC 2012 meeting.
From the introduction:
This paper is nothing but story telling, it narrates how some new unexpected
fundamental theoretical results have been obtained in Algebraic Topology,
produced by experimental evidence after numerous computations. These results
are complex, not yet fully proved, but the underlying algorithms are entirely
known, allowing us to implement them and to use them successfully...
Effective Homotopy of Fibrations.
Accepted in "Applicable Algebra in Engineering, Communication and Computing".
The notion of Solution of the Homotopical Problem for a simplicial set is defined and applied to Kan Simplicial Fibrations. Using this notion, the standard Serre exact sequence between the homotopy groups of the components of a fibration \(F \hookrightarrow E \rightarrow B\) becomes an effective tool computing the homotopy groups of \(F\) (resp. \(E\), \(F\)) when those of \(E\) and \(B\) (resp. those of \(F\) and \(B\), those of \(F\) and \(E\)) are known.
How Kenzo works.
See the abstract.
Computing All Maps into a Sphere.
Accepted for the ACM-SIAM Symposium on Discrete Algorithms (Kyoto, January 2012). Sole winner of the SODA-2012 Best Paper Award. An algorithm computing the group \([X,Y]\) of homotopy classes of continuous maps \(X \rightarrow Y\) under appropriate conditions (stable range). Mainly due to the Czech and German authors, using Constructive Algebraic Topology as the starting point. A long version has been accepted by JACM in 2014. This work opens an impressive collection of fascinating computational challenges in Algebraic Topology.
A user interface for computations in Algebraic Topology.
Abstract: fKenzo (= friendly Kenzo) is a graphical user interface providing a user-friendly front-end for the Kenzo system, a Common Lisp program devoted to Algebraic Topology. The fKenzo system provides the user interface itself, an XML intermediary generator-translator and, finally the Kenzo kernel. We describe in this paper the main points of fKenzo, and we explain also the advantages and limitations of fKenzo with respect to Kenzo itself. The text is separated into two parts, trying to cover both the user and the developer perspectives.
Published in Journal of Symbolic Computation (February 2011).
Discrete Vector Fields and Fundamental Algebraic Topology.
[Version 6.2, May 9, 2012.]
Version 5.6 on Arxiv.
Paper in preparation. The Discrete Vector Field technology is
systematically used to reconsider the basic homology equivalences of Algebraic
Topology through new eyes. Hoping significant improvements of the computer
programs working about effective homology.
See in particular the
news of November 2011.
Triangulations of complex projective spaces.
Included in the book «Contribuciones Científicas en Honor de MIRIAN ANDRÉS GÓMEZ». The Kenzo program is used to automatically produce triangulations of the complex projective spaces \(P^n\mathbb{C}\) as simplicial sets, more precisely of spaces having the right homotopy type. The homeomorphism question between the obtained objects and the projective spaces is open.
Effective Exact Couples.
Version 2.2 (April 2009). Paper in preparation. A totally new method to make effective standard homological algebra. This is version 2.2 (April 2009): minor correction with respect to version 2.1. The kernel of the method is defined and proved with an unusual level of details. The same for solving the extension problems.
A case study of A∞-structure.
How the Kenzo program can be used to study highly sophisticated algebraic structures, out of scope of pen and paper (Georgian Mathematical Journal, 2010, vol. 17, pp.57-77.).
Introduction to Combinatorial Homotopy Theory.
A short introduction to combinatorial Algebraic Topology. Used as lecture notes for a four hours lecture series at the Ictp-Map Summer School, Trieste, August 2008.
Ana Romero's thesis.
Title: Effective Homology and Spectral Sequences.
Defended on
November 13, 2007.
Genova Lecture Notes under the title
«Constructive Homological Algebra»; (154 pages).
Six presentation pdf files.
Eight Lisp-Demo files.
Abstract:
Standard homological algebra is not constructive, and this is frequently the source of serious problems when algorithms are looked for. In particular the usual exact and spectral sequences of homological algebra frequently are not sufficient to obtain some unknown homology or homotopy group. We will explain it is not difficult to fill in this gap, the main tools being on one hand, from a mathematical point of view, the so-called Homological Perturbation Lemma, and on the other hand, from a computational point of view, Functional Programming.
We will illustrate this area of constructive mathematics by applications in two domains:
a) Commutative Algebra frequently meets homological objects, in particular when resolutions are involved (syzygies). Constructive Homological Algebra produces new methods to process old problems such as homology of Koszul complexes, resolutions, minimal resolutions. The solutions so obtained are constructive and therefore more complete than the usual ones, an important point for their concrete use.
b) Algebraic Topology is the historical origin of Homological Algebra. The usual exact and spectral sequences of Algebraic Topology can be easily transformed into new effective versions, giving algorithms computing for example unknown homology and homotopy groups. In particular the effective version of the Eilenberg-Moore spectral sequence gives a very simple solution for the old Adams' problem: what algorithm could compute the homology groups of iterated loop spaces?
Machine programs and machine demonstrations will also concretely illustrate the theoretical results so obtained.
Koszul complexes and minimal resolutions.
Three documents about the effective homology of Koszul complexes.
-
A pdf presentation for talks given in many places about the methods allowing one to compute and use the effective homology of Koszul complexes.
-
An announcement about the strong relation between the effective homology of the Koszul complex of an A-module and its minimal resolution.
-
A Lisp-Kenzo demonstration of a computation of effective homology of a Koszul complex.
Computing Spectral Sequences.
Ana Romero's paper about the
exact relation between Effective Homology and Spectral Sequences.
Published in Journal of Symbolic Computation, 2006,
vol 41, pp 1059-1079.
Abstract: John McCleary insisted in his interesting textbook User's Guide to Spectral Sequences on the fact that the tool «spectral sequence» is not in the general situation an algorithm allowing its user to compute the looked-for homology groups. The present article explains how the notion of «Object with Effective Homology» on the contrary allows the user to recursively obtain all the components of the Serre and Eilenberg-Moore spectral sequences, when the data are objects with effective homology. In particular the computability problem of the higher differentials is solved, the extension problem at abutment is also recursively solved. Furthermore, these methods have been concretely implemented as an extension of the Kenzo computer program. Two typical examples of spectral sequence computations are reported.
Postnikov «Invariants» in 2004.
Julio Rubio and FS paper published in Georgian Mathematical Journal, 2005, vol 12, pp 139-155.
Abstract: The very nature of the so-called Postnikov invariants is carefully studied. Two functors, precisely defined, explain the exact nature of the connection between the category of topological spaces and the category of Postnikov towers. On one hand, these functors are in particular effective and lead to concrete machine computations through the general machine program Kenzo. On the other hand, the Postnikov «invariants» will be actual invariants only when an arithmetical decision problem – currently open – will be solved; it is even possible this problem is undecidable.
Computing with locally effective matrices.
Julio Rubio and FS paper published in International Journal of Computer Mathematics, 2005, vol 82, pp 1177–1189.
Abstract: In this work, we start from the naive notion of integer infinite matrix (i.e., the functions of the set ZN x N = {f : N x N -> Z}). Then, several undecidability results are established, leading to a convenient data structure for effective machine computations. We call this data structure a locally effective matrix. We study when (and how) the standard matrix calculus (Ker and CoKer computations) can be extended to the infinite case. We find again several undecidability barriers. When these limitations are overcome, we describe effective procedures for computing in the locally effective case. Finally, the role played by these data structures in the development of real symbolic computation systems for algebraic topology (based on the effective homology notion) is illustrated.
Algebraic Models for Homotopy Types.
Julio Rubio and FS paper published in Homology, Homotopy and Applications, 2005, vol7, pp139–160
Abstract: The classical problem of algebraic models for homotopy types is precisely stated here in terms of our ability to compute with the models. Two different natural statements for this problem are produced, the simplest one being entirely solved by the notion of SSEH-structure, due to the authors. Other tentative solutions, Postnikov towers and E∞-chain complexes, are considered and compared with the SSEH-structures. In particular, an imprecision in the usual definition of the k-“invariants” is explained, which implies we seem far from a solution for the ideal statement of our problem. On the positive side, the computability problem for the Postnikov towers is solved.
The Zentralbaltt review qualifies the style of this paper as somewhat irritating. Maybe the truth table of ordinary mathematics is to be enriched.
Constructive Algebraic Topology.
Julio Rubio and FS paper published in Bulletin des Sciences Mathématiques, 2002, vol 126, pp 389–412
Abstract: The classical “computation” methods in Algebraic Topology most often work by means of highly infinite objects and in fact are not constructive. Typical examples are shown to describe the nature of the problem. The Rubio–Sergeraert solution for Constructive Algebraic Topology is recalled. This is not only a theoretical solution: the concrete computer program Kenzo has been written down which precisely follows this method. This program has been used in various cases, opening new research subjects and producing in several cases significant results unreachable by hand. In particular the Kenzo program can compute the first homotopy groups of a simply connected arbitrary simplicial set.
K, objet du 3ème type (in French).
Published in Gazette des Mathématiciens, 2000, vol 86, pp 29-45.
Expository report about the theoretical and computer work of the author and his collaborators about the Effective Homology theory.
The Homology of Iterated Loop Spaces.
Article by V. A. Smirnov, appendix of FS. Published in Forum Mathematicum, 2002, vol 14, pp 345-381.
Theoretical solution by the author and computations by hand of homology groups (with respect to the field Z/2Z) of iterated loop spaces. The appendix is a report about related computer results (with respect to the ring Z).
Maple expliqué (in French).
Début d'un texte détaillant le fonctionnement et l'utilisation de Maple.
Chapitres rédigés:
- Premières sessions Maple.
- Le modèle «Read-Eval-Print» de Maple.
- Les types de donnes numériques.
- Listes, ensembles, suites et tables.
- Programmation.
- Procédures.
Common Lisp, Typing and Mathematics.
Text written as lecture notes for a three hours talk given on September 11, 2001(!), a satellite talk of the EACA Meeting at Ezcaray (Spain).
This paper (45p.) is a presentation of Common Lisp for Mathemacians, more exactly a presentation of the Common Lisp Object System (= CLOS) which is now the main constituent of the language achitecture. The nature of this paper is didactic, with simple examples that can be repeated on any ANSI Common Lisp environment. Sections:
- Introduction.
- Common Lisp Object System.
- What typing is.
- CLOS and mathematical structures.
- CLOS and the Kenzo program.
Constructive Algebraic Topology.
Lecture Notes for the course with the same title at the Summer School «Fundamental Algebraic Topology» in June-July 1997 at the Fourier Institute, Grenoble.
Sections:
- Introduction.
- General Organization.
- Functional programming in Lisp.
- Functional programming and infinite simplicial sets.
- A mathematical definition is not necessarily constructive.
- The EAT program.
- EAT and the loop spaces.
- The appropriate mathematical language.
- The general organization revisited.
- Perturbation lemma.
- Bicomplexes.
- Tensor products.
- Eilenberg-Zilber.
- Serre spectral sequence.
Topological Constructors.
Lecture Notes for an introductory course in the 1997 Grenoble Summer School «Fundamental Algebraic Topology».
Sections:
- Introduction.
- CW-complexes.
- The category Delta.
- Simplicial sets.
The Computability Problem in Algebraic Topology.
The first published paper about Effective Homology. The role of the Basic Perturbation «Lemma», discovered by Julio Rubio when preparing his thesis in 1989, was not yet known, which makes this paper rather difficult!
From the introduction: Hilbert's dream actually was a dream. But a new subject for research was thus opened: studying what mathematical theories are in fact open to algorithmic processes. A concrete example will help us to explain this idea. Novikov proved the nonexistence of a general algorithm for solving the word problem in a finitely presented group. But on the contrary Tartakovskii proved that this problem is solvable for a large class of groups; for example Magnus had proved before Novikov's work the existence of a solution for a group with one relation.
This paper is devoted to such a result. Here it is proved that almost every reasonable computability problem in homological algebra and algebraic topology has a positive solution. There remains a unique limitation, as frequently in algebraic topology: simple connectivity hypotheses must often be satisfied; otherwise it is easy to find problems the non-computability of which results from Novikov's theorem. For example there does not exist a general algorithm allowing to decide whether a finite simplicial complex is simply connected.
Effective Homology, a survey.
A writing of something like the GCD of several talks given in Summer 1992 in Japan (Sapporo, Morioka, Urawa, Tokyo, Kyoto, Nara, Osaka, Hiroshima) during a JSPS (Japanese Society for Promotion of Science) stay in Summer 1992.
Utilisation des flottants du hardware pour le calcul rationnel exact (in French).
Paper published in Mémoires de la Société Mathématique de France, 1977, vol 49-50, pp 187-194.
How it is possible in linear algebra to work simultaneously with exact rational computations and necessarily approximate floating interval computations.