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.
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.
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.
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.
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 Z^{N 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.
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.
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.
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.
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).
Début d'un texte détaillant le fonctionnement et l'utilisation de Maple.
Chapitres rédigés:
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:
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:
Lecture Notes for an introductory course in the 1997 Grenoble Summer School «Fundamental Algebraic Topology».
Sections:
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.
How it is possible in linear algebra to work simultaneously with exact rational computations and necessarily approximate floating interval computations.