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 → E → B becomes an effective tool computing the homotopy groups of F (resp. E, B) 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 → 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 is in preparation. 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 PnC 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.