A Haskell rewrite of Kenzo, a collection of algorithms for 'effective algebraic topology'. The algorithms and implementations in Kenzo were created by Francis Sergeraert, Julio Rubio Garcia, Xavier Dousson, Ana Romero and many collaborators.

Writing it from scratch myself is the only chance I have of understanding it!

See the examples/ folder.

...
> let x = totalSpace s3 (Wbar kz1) fibration
> putStr "π₄ S³ is: "
> print (homology x !! 4)
π₄ S³ is: ℤ/2

> homology (Wbar (WbarDiscrete (Zmod 3)))
[ℤ,0,ℤ/3,0,ℤ/3,0,ℤ/(3^2),ℤ/3,ℤ/3,ℤ/3,ℤ/3 ⊕ ℤ/3,^C

A simplicial set X is described by a type a, containing whatever data is required to specify X, and a type GeomSimplex a, whose elements correspond to non-degenerate simplices (in Kenzo called 'geometric simplices'). Like Kenzo we also allow a predicate on GeomSimplex a specifying when an element actually describes a geometric simplex and when it is 'spurious'.

An actual simplex of X is a geometric simplex together with a 'formal degeneracy operator', which is a list of degeneracy operators in a normal form. Face maps are implemented as functions from geometric simplices to (possibly degenerate) simplices, and the extension of these face maps to all simplices is forced by the simplicial identities.

A simplicial set is of finite type if there is a finite number of geometric simplices for each dimension, and there is a function giving a list of these simplices for any dimension n. It is not required that there are finitely many geometric simplices overall.

The normalised chain complex N(X) of X has each N(X)_n given by the free abelian group on the set of nondegenerate n-simplices of X, with the boundary of a simplex calculated similar to usual (the alternating sum of face maps), but ignoring any degenerate faces.

If C(X) is the ordinary chain complex of simplicial chains of X, the quotient map C(X) -> N(X) is a quasi-isomorphism, and so if X is of finite type, then the homology of X can be computed via N(X).

But many unavoidable simplicial sets (like K(ℤ,n) and loop spaces ΩX) are not of finite type, and so we need some other way to calculate their homology. This is where 'effective homology' comes in.

A reduction between chain complexes C and D is a strong deformation retract of chain complexes. The data of a reduction unwinds to a triple (f : C -> D, g : D -> C, h : C -> C) where f and g are degree 0, the homotopy operator h is degree 1, and certain equations involving these hold. A (strong chain) equivalence between two chain complexes C and D is a span of reductions l : E -> C and r : E -> D.

An effective homology structure on C is an equivalence between C and a chain complex F of finite type.

A simplicial set with effective homology is a simplicial set X equipped with an effective homology structure on N(X).

The point of Kenzo is that although constructions on simplicial sets sometimes do not preserve levelwise finiteness, they do extend to effective homology structures. And so if we begin with a finite simplicial complex and perform some constructions using it, then we can often compute the homology of the result even if the actual simplicial sets are now far too complicated to get a handle on.

• Definitions
  • Chain Complex
  • Bicomplex
    • Tot
  • Reduction
    • Perturbation
  • Strong Equivalence
    • Composition via span
• Constructions
  • Tensor (of chain complex)
    • Functoriality
  • Hom (of chain complex)
  • 'Bicone' (specialised pushout for surjections)
  • Bar
    • Commutative algebra structure
    • Functoriality
  • Cobar
    • Of 1-reduced
    • Of 0-reduced
    • Functoriality

• Definitions
  • Simplicial Set
  • Simplicial Morphism
  • Simplicial Group
  • Kan Structure
  • SSet With Effective Homology
  • Principal Fibrations
  • Discrete Vector Fields
  • Coalgebra Structure on Chains
  • Algebra Structure on Chains of Groups
  • Kan Structure on Chains of Groups
• Finite Examples
  • Spheres
    • Treat S¹ separately (not 1-reduced)
  • Moore Spaces
  • Projective Spaces
  • Lens Spaces
• Eilenberg-MacLane Spaces
  • K(ℤ,1)
  • K(ℤ/2,1) (Can be made particularly efficient)
  • K(ℤ/p,1)
• Constructions
  • Products
    • Group structure
  • Total Space of Principal Fibration
  • Loop Space
    • Of 1-reduced
    • Of 0-reduced
    • Group structure
    • Canonical twisting function X -> GX
  • Classifying Space
    • For 0-reduced group
    • For non-reduced group
    • Special case for discrete groups
    • Group Structure
    • Canonical twisting function WG -> G
  • Suspension
    • 0-reduced
    • General Kan suspension
  • Pushouts (of 1-reduced sSets)
  • Other Finite Homotopy Colimits
  • 'Nerve' taking a ChainComplex back to a sAb?

• Classifying Spaces
  • Direct Reduction of K(ℤ,1) to S¹
  • Of 0-reduced Abelian sGrps
  • Of General sGrps
• Products
  • Eilenberg-Zilber reduction
  • Use specialised contraction maps for efficiency
• Fibrations
  • Total Space from Base and Fibre ('Serre' problem)
    • 1-reduced Fibre
    • 0-reduced Fibre
  • Fibre from Base and Total Space ('Eilenberg-Moore' problem)
• Loop Space
  • 1-reduced
  • 0-reduced
• Colimits
  • Suspension
  • Pushouts (of 1-reduced sSets)
  • Finite Homotopy Colimits
• Discrete Vector Fields
  • Induced Reduction
  • Products
  • Fibrations
  • K(ℤ,1)
    • Naive but easy
    • Polynomial time but complicated
  • K(ℤ/n,1)?
  • Classifying Spaces for 0-reduced sAb
• Homotopy Groups
  • Whitehead Tower (for 1-reduced sSet)
  • Postnikov Tower?
• Cohomology Operations
  • Over fields using "minimal models" and

• Fix space leaks, jeez
• Pretty-printing for everything (unicode sub/superscripts in output?)
• Docs for everything
• Move this list to Github issues
• Consolidate some files? Eg. Sum, Shift into ChainComplex
• Use bit operations eg from bits-extra for degeneracy operators.
• Short-circuits: e.g. composing with zero/id for morphism/reduction/equivalence
• Make sure things are being aggressively inlined
• Make homology calculation do less work: should just need SNF of one matrix and the rank of another.
• Improve Smith normal form code, would be better to call out to some existing library instead of rolling our own. The options appear to be LinBox or FLINT. The former appears to support sparse matrices better
• Check homology of K(G,n) calculations against known results
• Add methods to produce representatives of homology classes
• Rewrite Bar to be a perturbed TensorCoalgebra?
• Rename basepoint to geomBasepoint say

• I have switched a little terminology: I believe Kenzo uses 'effective' for finite-type things and 'locally effective' for what I am calling effective things, but I find this a bit confusing.
• In Kenzo, every sSet is conflated with its chain complex of normalised chains, here I have kept the two separate.
• Avoid over-engineering the Haskell as much as possible.
• That being said, the use of Constrained.Category is a bit of a mess.
• There may be a way to unify some of the algorithms via bicomplexes and the 'generalised Eilenberg-Zilber theorem' relating the diagonal and total complexes. But the EZ-theorem only gives a strong deformation retract in special cases, in general it is just a chain homotopy equivalence.
• The classifying space functor Wbar factors through the 'total bisimplicial set' functor. But it would be difficult to describe the total functor on bisimplicial spaces algorithmically, because its definition involves the equaliser of certain face maps. So it only makes sense to implement bicomplexes and not bisimplicial sets.
• Auto-formatting the code: fourmolu -o -XTypeApplications -i $(find . -name '*.hs')
• Running Kenzo with SBCL:

  > rlwrap sbcl
  (require :asdf)
  (load "kenzo.asd")
  (asdf:load-system "kenzo")
  (in-package :kenzo)
  
  (finite-ss-table '(a b 1 c (b a)))
  

  etc.
• classes.lisp in Kenzo contains the meaning of some of the 4 letter abbreviations
  • ABSM = ABstract SiMplex
  • GMSM = GeoMetric SiMplex
  • CMBN = CoMBinatioN
  • CFFC = CoeFFiCient
  • GNRT = GeNeRaTor
  • CMPR = CoMPaRison
  • CMPRF = CoMPaRison Function
  • ICMBN = Internal-CoMBiNation
  • STRT = STRaTegy
  • bsgn = BaSe GeNerator
  • dffr = DiFFeRential
  • grmd = GRound MoDule
  • efhm = EFfective HoMology
  • idnm = IDentification NuMber
  • orgn = ORiGiN
  • vctr = VeCToR
  • intr-mrph = INTeRnal-MoRPHism (the class of actual functions implementing a morphism of simplicial sets or chain complexes)
  • sbtr = SuBTRact
  • crpr = CarRtesian PRoduct
  • BRGN = BaR GeNerator
  • TNPR = TeNsor PRoduct
• Unguessable CL functions
  • (ash x n) = bit shift x left by n
  • (add x y) and (sbtr x y) can sometimes actually be a use of the perturbation lemma(!!), depending on the types of the arguments.

• Kenzo homepage
• Kenzo documentation, likely out of date with the code in places
• 'Official' Kenzo mirror on GitHub, there are three different versions of the code here, I am not clear on what is gained/lost between them. There are online Jypter notebooks that let you play with Kenzo (I believe Kenzo-9) without having to figure out how to install and operate a Common Lisp environment
• Fork by Ana Romero + collaborators, has some added features over the mirror above, worth looking at resolutions.lisp and homotopy.lisp, but is missing all the discrete vector field code
• Modules written by Ana Romero, mostly to do with spectral sequences

Everything even remotely relevant to effective algebraic topology that I can find (not all of which is relevant for implementation). Some of the documents have multiple versions; I have tried to link to the most recent in each case. Some material is repeated in different references.