Skip to main content

logicaffeine_proof/
kan_complex.rs

1//! Actually **having** an ∞-groupoid — not its invariants, the object itself, with its defining
2//! property machine-verified.
3//!
4//! Everything in `progress_complex`/`cubical` computed *invariants* (Betti numbers) of *spaces*. That is
5//! not the same as possessing the ∞-groupoid: by the homotopy hypothesis the simplicial model of an
6//! ∞-groupoid is a **Kan complex** — a simplicial set in which every *horn* (a simplex with one face
7//! missing) can be filled. Here we build such an object directly: the **nerve of a group**, whose
8//! degree-`n` simplices are `Gⁿ` (chains of composable arrows), and we *verify the Kan condition* —
9//! every horn fills — in degrees 2 and 3. The nerve of `Aut(F)` is exactly `BG = K(Aut(F),1)`, the
10//! classifying space the symmetry tower named, so this is that ∞-groupoid, now had as an object.
11//!
12//! It is honestly the **1-truncated** one: inner horns fill *uniquely*, the hallmark of the nerve of a
13//! 1-groupoid (no genuine higher cells). A non-truncated ∞-groupoid — nontrivial `π_{≥2}`, inner horns
14//! with *several* fillers, the homology ladder's higher `πₙ` assembled into one coherent complex with
15//! its k-invariants — is the frontier this does NOT yet reach, and we say so in the test that proves the
16//! uniqueness.
17
18use crate::two_group::FiniteGroup;
19
20/// The `i`-th face `d_i` of a degree-`n` simplex `(g_1, …, g_n) ∈ Gⁿ` of the nerve: drop the first arrow
21/// (`i=0`), drop the last (`i=n`), or compose the adjacent pair (`0 < i < n`).
22fn face(g: &FiniteGroup, s: &[usize], i: usize) -> Vec<usize> {
23    let n = s.len();
24    if i == 0 {
25        return s[1..].to_vec();
26    }
27    if i == n {
28        return s[..n - 1].to_vec();
29    }
30    let mut out = s.to_vec();
31    out[i - 1] = g.mul[s[i - 1]][s[i]];
32    out.remove(i);
33    out
34}
35
36/// Every degree-`n` simplex of the nerve — all of `Gⁿ`.
37fn all_simplices(g: &FiniteGroup, n: usize) -> Vec<Vec<usize>> {
38    let mut out: Vec<Vec<usize>> = vec![vec![]];
39    for _ in 0..n {
40        let mut next = Vec::with_capacity(out.len() * g.order());
41        for s in &out {
42            for e in 0..g.order() {
43                let mut t = s.clone();
44                t.push(e);
45                next.push(t);
46            }
47        }
48        out = next;
49    }
50    out
51}
52
53/// Enumerate every **compatible horn** `Λⁿ_k` — an assignment of a degree-`(n-1)` simplex to each face
54/// position `i ≠ k` satisfying the simplicial identities `d_i x_j = d_{j-1} x_i` (`i < j`) — and call
55/// `each(filler_count)` with how many degree-`n` simplices fill it.
56fn for_each_horn(g: &FiniteGroup, n: usize, k: usize, mut each: impl FnMut(usize)) {
57    let lower = all_simplices(g, n - 1);
58    let tops = all_simplices(g, n);
59    let positions: Vec<usize> = (0..=n).filter(|&i| i != k).collect();
60    let base = lower.len();
61    let total: u128 = (base as u128).pow(positions.len() as u32);
62    for idx in 0..total {
63        // decode the assignment of a lower simplex to each position
64        let mut x = idx;
65        let horn: Vec<(usize, &Vec<usize>)> = positions
66            .iter()
67            .map(|&p| {
68                let a = (x % base as u128) as usize;
69                x /= base as u128;
70                (p, &lower[a])
71            })
72            .collect();
73        // compatibility: d_i x_j = d_{j-1} x_i for i < j
74        let compatible = horn.iter().enumerate().all(|(a, &(i, xi))| {
75            horn[a + 1..]
76                .iter()
77                .all(|&(j, xj)| face(g, xj, i) == face(g, xi, j - 1))
78        });
79        if !compatible {
80            continue;
81        }
82        let fillers = tops
83            .iter()
84            .filter(|y| horn.iter().all(|&(p, xp)| &face(g, y, p) == xp))
85            .count();
86        each(fillers);
87    }
88}
89
90/// Does the nerve satisfy the **Kan condition** for horns `Λⁿ_k` — does every compatible horn fill?
91pub fn kan_fills(g: &FiniteGroup, n: usize, k: usize) -> bool {
92    let mut ok = true;
93    for_each_horn(g, n, k, |fillers| ok &= fillers >= 1);
94    ok
95}
96
97/// Does every compatible **inner** horn (`0 < k < n`) fill *uniquely*? Unique inner fillers are the
98/// signature of a 1-truncated nerve — the ∞-groupoid is exactly `K(G,1) = BG`, no genuine higher cells.
99pub fn inner_horns_fill_uniquely(g: &FiniteGroup, n: usize, k: usize) -> bool {
100    assert!(0 < k && k < n, "inner horns only");
101    let mut unique = true;
102    for_each_horn(g, n, k, |fillers| unique &= fillers == 1);
103    unique
104}
105
106/// All `A`-valued cochains on `BG_k` — functions `BG_k = Gᵏ → A = Z/modulus`.
107fn nerve_cochains(g: &FiniteGroup, modulus: usize, k: usize) -> Vec<Vec<usize>> {
108    let size = all_simplices(g, k).len();
109    let mut out: Vec<Vec<usize>> = vec![vec![]];
110    for _ in 0..size {
111        let mut next = Vec::with_capacity(out.len() * modulus);
112        for t in &out {
113            for v in 0..modulus {
114                let mut u = t.clone();
115                u.push(v);
116                next.push(u);
117            }
118        }
119        out = next;
120    }
121    out
122}
123
124/// Simplicial coboundary `δ : Cᵏ(BG; A) → Cᵏ⁺¹` from the **nerve's own faces**:
125/// `(δφ)(σ) = Σᵢ (−1)ⁱ φ(dᵢ σ)`.
126fn nerve_coboundary(g: &FiniteGroup, modulus: usize, k: usize, phi: &[usize]) -> Vec<usize> {
127    let sk = all_simplices(g, k);
128    let idx: std::collections::HashMap<Vec<usize>, usize> = sk
129        .iter()
130        .cloned()
131        .enumerate()
132        .map(|(i, s)| (s, i))
133        .collect();
134    let skp1 = all_simplices(g, k + 1);
135    let mut out = vec![0usize; skp1.len()];
136    for (j, sigma) in skp1.iter().enumerate() {
137        let mut val = 0i64;
138        for i in 0..=(k + 1) {
139            let f = face(g, sigma, i);
140            let s = if i % 2 == 0 { 1 } else { -1 };
141            val += s * phi[idx[&f]] as i64;
142        }
143        out[j] = val.rem_euclid(modulus as i64) as usize;
144    }
145    out
146}
147
148/// The simplicial cohomology `|Hⁿ(BG; A)|` of the nerve `BG = K(G,1)`, computed from the nerve's own
149/// face maps. By the Eilenberg–MacLane representing property `Hⁿ(BG; A) = [BG, K(A,n)]`; we confirm it
150/// equals the algebraic **group cohomology** `Hⁿ(G; A)`, so the spectrum represents — on the symmetry's
151/// classifying space — exactly group cohomology, the home of the Postnikov k-invariants.
152pub fn nerve_cohomology_size(g: &FiniteGroup, modulus: usize, n: usize) -> usize {
153    let cocycles = nerve_cochains(g, modulus, n)
154        .into_iter()
155        .filter(|phi| nerve_coboundary(g, modulus, n, phi).iter().all(|&x| x == 0))
156        .count();
157    let mut coboundaries: std::collections::HashSet<Vec<usize>> = std::collections::HashSet::new();
158    for psi in nerve_cochains(g, modulus, n - 1) {
159        coboundaries.insert(nerve_coboundary(g, modulus, n - 1, &psi));
160    }
161    cocycles / coboundaries.len()
162}
163
164#[cfg(test)]
165#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/kan_complex/tests.rs"]
166mod tests;