The classifying space and its homology

BG is built from the group itself, with no choices: one vertex, one edge for each non-identity element, one triangle for each pair of non-identity elements (recording their product), and so on in every dimension, with (|G| - 1)^n cells in dimension n. It is infinite, but the homology up to a given degree needs only finitely many cells.

import scala.language.experimental.modularity
import org.appliedtopology.tda4j.*
import org.appliedtopology.tda4j.sset.*

val s3 = FiniteGroup.symmetric(3)
val s3Homology = Seq(2, 3).map(p => p -> ClassifyingSpace.bettiNumbers(s3, 4, p)).toMap
// 2 -> Vector(1, 1, 1, 1, 1)     3 -> Vector(1, 0, 0, 1, 1)

bettiNumbers(group, maxDegree, p) gives the dimensions of H_n(G; F_p) for n up to maxDegree, with coefficients in the field with p elements. The answers carry group theory that you can check by hand:

• Over p = 2 the answer is one class in every degree, 1, 1, 1, 1, 1, exactly that of the cyclic group of order 2. That is not an accident: the symmetric group on three letters has a subgroup of order 2 whose index, 3, is odd, and an odd index is invisible over the field with 2 elements.
• Over p = 3 the pattern is 1, 0, 0, 1, 1: classes in degrees 3 and 4 (and, continuing, 7, 8, ...), which is what the cyclic subgroup of order 3 would contribute once you account for how the element of order 2 acts on it.

A chain of subgroups

Now the persistent version. Take the symmetric group on four letters, 24 permutations, and a chain of four subgroups of it: the group ⟨(01)⟩ generated by swapping the first two letters (order 2); ⟨(01), (23)⟩, generated by two independent swaps (order 4); the dihedral group of order 8, the symmetries of a square, which contains both; and all of S_4 (order 24).

val (s4, generators) = FiniteGroup.permutationGroup(
  4,
  Seq(Seq(1, 0, 2, 3), Seq(0, 1, 3, 2), Seq(2, 3, 0, 1), Seq(1, 2, 3, 0))     // (01), (23), (02)(13) and the 4-cycle (0123)
)
val Seq(swap01, swap23, doubleSwap, _) = generators
val chain = Seq(
  s4.subgroupGeneratedBy(Seq(swap01)),
  s4.subgroupGeneratedBy(Seq(swap01, swap23)),
  s4.subgroupGeneratedBy(Seq(swap01, swap23, doubleSwap)),
  (0 until s4.order).toSet
)
chain.map(_.size)         // List(2, 4, 8, 24)

A permutation is its list of images (Seq(1, 0, 2, 3) sends 0 to 1, 1 to 0 and fixes 2 and 3), and permutationGroup builds the group they generate and returns the position of each of your generators in it. The filtration value of a simplex of BG is the position in the chain of the first subgroup containing every element it uses, so the four subgroups are at times 0, 1, 2, 3:

def bars(prime: Int) =
  ClassifyingSpace.persistentGroupHomology(s4, chain, maxDegree = 2, prime = prime).triples.groupBy(identity).view.mapValues(_.size).toMap

bars(2)
// (0, 0.0, Infinity), (1, 0.0, Infinity), (1, 1.0, 2.0), (1, 2.0, 3.0),
// (2, 0.0, Infinity), (2, 1.0, 2.0), (2, 1.0, Infinity), (2, 2.0, 3.0)    each once

persistentGroupHomology returns a persistence diagram: triples lists its bars, and each bar also carries a representative, a cycle of BG built from the subgroup where its class is born. A bar (n, i, j) says: a class of degree n first appears in the homology of the i-th subgroup and is gone from the j-th (killed, or identified with another class, when you pass to the bigger group); Infinity means it is still there in S_4 itself. Reading the degree-1 bars:

• (1, 0, ∞): the class from the first subgroup survives all the way to S_4. It is the sign of a permutation (the map from S_4 to the group of order 2), which is the one class in H_1(S_4).
• (1, 1, 2): passing to ⟨(01), (23)⟩ brings a new class (the second swap) which dies when we pass to the dihedral group of order 8, in which the two swaps are conjugate, hence the same class.
• (1, 2, 3): the dihedral group has a further class of its own, which dies in S_4, whose first homology is just the sign.

And in degree 2, there are four bars ((2, 0, ∞), (2, 1, ∞), and two short ones), two surviving to S_4: its second homology over the field with 2 elements has dimension 2, as theory says. Two things to notice. First, nothing essential is born at the last step: every class of S_4 already lives in the dihedral group of order 8, the subgroup of order 8, a Sylow 2-subgroup. That is a theorem (classes of a group at a prime come from its Sylow subgroup), and here you can watch it happen. Second, over the field with 3 elements the barcode is just a point,

bars(3)       // (0, 0.0, Infinity) only

because every subgroup in the chain is a 2-group and S_4 has no odd-prime classes in these degrees: the barcode over a prime p sees only what the p-part of the group contributes.

The cost

The size of BG is the catch. It has (|G| - 1)^n cells in dimension n, and computing the homology in degree k needs the cells up to dimension k + 1:

When the chain can be refined to a series of subgroups, each normal in the next with prime index (always possible for a group whose order is a prime power, and for chains like 1 < V_4 < A_4 < S_4 in a solvable group), the library computes on a much smaller complex with the same barcode: Brown's collapse of BG (CollapsedNerve), built from a rewriting system for the group (RewritingSystem.refining(group, chain)), whose representatives are mapped back to cycles of BG. For S_4 it has 10, 20 and 35 cells in dimensions 2, 3 and 4, instead of 529, 12,167 and 279,841:

val kleinFour = s4.subgroupGeneratedBy(Seq(s4.multiply(swap01, swap23), doubleSwap))
val alternating = s4.subgroupGeneratedBy(kleinFour + FiniteGroup.elementOfPermutation(s4, Seq(1, 2, 0, 3)))
val collapsed = CollapsedNerve(RewritingSystem.refining(s4, Seq(kleinFour, alternating)).toOption.get)
val collapsedCells = (2 to 4).map(n => collapsed.criticalCells(n).size)     // Vector(10, 20, 35)

ClassifyingSpace.bettiNumbers and persistentGroupHomology use the collapse by themselves whenever the chain refines, which puts higher degrees in reach:

val s4Homology = Seq(2, 3).map(p => p -> ClassifyingSpace.bettiNumbers(s4, 4, p)).toMap
// 2 -> Vector(1, 1, 2, 3, 3)     3 -> Vector(1, 0, 0, 1, 1)

Over p = 2 these are the dimensions of the cohomology ring of S_4, polynomials in classes of degrees 1, 2 and 3 with one relation in degree 4; over p = 3 they are those of S_3 from the first section: at the prime 3, S_4 looks like the normalizer of its subgroup of order 3, which is a copy of S_3. The chain of the previous section has no such refinement (the dihedral group of order 8 is not normal in S_4, and no subgroup lies strictly between them), so its barcode was computed on BG itself:

val throughDihedral = RewritingSystem.refining(s4, chain).isLeft     // true

The collapse still grows exponentially with the degree, only much more slowly, and a group that is not solvable, such as S_5, always takes the full construction.

The whole script

import scala.language.experimental.modularity
import org.appliedtopology.tda4j.*
import org.appliedtopology.tda4j.sset.*

val s3 = FiniteGroup.symmetric(3)
val s3Homology = Seq(2, 3).map(p => p -> ClassifyingSpace.bettiNumbers(s3, 4, p)).toMap

val (s4, generators) = FiniteGroup.permutationGroup(
  4,
  Seq(Seq(1, 0, 2, 3), Seq(0, 1, 3, 2), Seq(2, 3, 0, 1), Seq(1, 2, 3, 0))
)
val Seq(swap01, swap23, doubleSwap, _) = generators
val chain = Seq(
  s4.subgroupGeneratedBy(Seq(swap01)),
  s4.subgroupGeneratedBy(Seq(swap01, swap23)),
  s4.subgroupGeneratedBy(Seq(swap01, swap23, doubleSwap)),
  (0 until s4.order).toSet
)

def bars(prime: Int) =
  ClassifyingSpace.persistentGroupHomology(s4, chain, maxDegree = 2, prime = prime).triples.groupBy(identity).view.mapValues(_.size).toMap

val overF2 = bars(2)
val overF3 = bars(3)

val kleinFour = s4.subgroupGeneratedBy(Seq(s4.multiply(swap01, swap23), doubleSwap))
val alternating = s4.subgroupGeneratedBy(kleinFour + FiniteGroup.elementOfPermutation(s4, Seq(1, 2, 0, 3)))
val collapsed = CollapsedNerve(RewritingSystem.refining(s4, Seq(kleinFour, alternating)).toOption.get)
val collapsedCells = (2 to 4).map(n => collapsed.criticalCells(n).size)

val s4Homology = Seq(2, 3).map(p => p -> ClassifyingSpace.bettiNumbers(s4, 4, p)).toMap
val throughDihedral = RewritingSystem.refining(s4, chain).isLeft