
Abstract:The Smith reduction is a basic tool when analyzing integer
matrices up to equivalence, and the KannanBachem (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.

Abstract: The EilenbergZilber (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.
Sixtyfive 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 spath, a 2dimensional
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 RubioMorace formula for the
EZhomotopy. Other striking applications will be the subject of other papers.

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 wellknown long exact sequence of homotopy of a
fibration defined by JeanPierre 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).

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

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.7181.
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: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.

The first try to make constructive the BousfieldKan spectral sequence.
This spectral sequence is the combinatorial basic tool underlying the Adams
spectral sequence. Published in Foundations of Computational Mathematics, May 2016.

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

"Long version" of the SODA paper below. Accepted at JACM.

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.

A curious and amazing complexity problem, for a terribly elementary algorithm,
but with exponential complexity in his ordinary form.

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

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.


Sole winner of the SODA2012 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.

Abstract: fKenzo (= friendly Kenzo) is a graphical user interface
providing a userfriendly frontend for the Kenzo system, a Common Lisp program
devoted to Algebraic Topology. The fKenzo system provides the user interface
itself, an XML intermediary generatortranslator 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).

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.

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.

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.

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.5777.).

A short introduction to combinatorial Algebraic Topology. Used as lecture notes
for a four hours lecture series at the IctpMap
Summer School, Trieste, August 2008.

Ana Romero's thesis.
Title: Effective Homology and Spectral Sequences.
Defended on
November 13, 2007.

Genova Summer School (August 28  September 2, 2006)
Genova Lecture Notes under the title
«Constructive Homological Algebra»; (154 pages).
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 socalled 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 EilenbergMoore
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 Amodule and its minimal resolution.

A LispKenzo demonstration of a computation of
effective homology of a Koszul complex.

Ana Romero's paper about the
exact relation between Effective Homology and Spectral Sequences.
Published in Journal of Symbolic Computation, 2006,
vol 41, pp 10591079.
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 lookedfor 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 EilenbergMoore 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 139155.
Abstract: The very nature of the socalled 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 SSEHstructure, due to the authors. Other tentative
solutions, Postnikov towers and E_{∞}chain complexes, are
considered and compared with the SSEHstructures. 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 2945.
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 345381.
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:

Premières sessions Maple.

Le modèle «ReadEvalPrint» de Maple.

Les types de donnes numériques.

Listes, ensembles, suites et tables.

Programmation.

Procédures.

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.

Lecture Notes for the course with the same
title at the Summer School «Fundamental Algebraic Topology»
in JuneJuly 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.

EilenbergZilber.

Serre spectral sequence.

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

Introduction.

CWcomplexes.

The category Delta.

Simplicial sets.

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

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.

Paper published in Mémoires de la Société Mathématique
de France, 1977, vol 4950, pp 187194.
How it is possible in linear algebra to work simultaneously with exact
rational computations and necessarily approximate floating interval
computations.

FS Thesis published in Annales Scientifiques de
l'Ecole Normale Supérieure, 1972, 4^{ème} Série, Tome 5, pp
599660.