Francis Sergeraert and Collaborators' Papers.

Genova Lecture Notes under the title «Constructive Homological Algebra»; (154 pages).

Eight Lisp-Demo files. Genova-1-Lisp-Demo Genova-2-Lisp-Demo Genova-3-Lisp-Demo Genova-4-Lisp-Demo Genova-5-Lisp-Demo Genova-6-Lisp-Demo Carlsson-Lisp-Demo Complexity-Lisp-Demo

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.

• 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:

1. Premières sessions Maple.
2. Le modèle «Read-Eval-Print» de Maple.
3. Les types de donnes numériques.
4. Listes, ensembles, suites et tables.
5. Programmation.
6. 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:

1. Introduction.
2. Common Lisp Object System.
3. What typing is.
4. CLOS and mathematical structures.
5. 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:

1. Introduction.
2. General Organization.
3. Functional programming in Lisp.
4. Functional programming and infinite simplicial sets.
5. A mathematical definition is not necessarily constructive.
6. The EAT program.
7. EAT and the loop spaces.
8. The appropriate mathematical language.
9. The general organization revisited.
10. Perturbation lemma.
11. Bicomplexes.
12. Tensor products.
13. Eilenberg-Zilber.
14. Serre spectral sequence.

• Topological Constructors.

Lecture Notes for an introductory course in the 1997 Grenoble Summer School «Fundamental Algebraic Topology».

Sections:

1. Introduction.
2. CW-complexes.
3. The category Delta.
4. 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.

• 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.