Skip to main content

logicaffeine_proof/
eilenberg_maclane.rs

1//! The general **Eilenberg–MacLane construction `K(A, n)`** — one engine, every rung of the tower.
2//!
3//! `two_type` built `K(A, 2)` by hand. Every space in the Postnikov tower is glued from `K(πₙ, n)`'s, so
4//! the honest way to "keep climbing" is to build the *general* `K(A, n)` for any `n`, not a fresh module
5//! per dimension. This is the Dold–Kan model `Γ(A[n])`: an `m`-simplex is an `A`-labeling of the
6//! order-preserving **surjections `[m] ↠ [n]`** (the chain complex is concentrated in degree `n`, so a
7//! face that fails to stay surjective dies — `C_{n−1} = C_{n+1} = 0`). It is a simplicial abelian group,
8//! hence a Kan complex, and we verify by enumeration, for `n = 2, 3`:
9//!
10//! - **`πₙ = A`**: the inner horn at degree `n` has `|A|` fillers — the `n`-cells.
11//! - **Kan**: every horn fills (the face-tuple map is onto the compatible horns).
12//! - **exactly `n`-truncated**: inner horns at degree `n + 2` fill *uniquely* — no `π_{n+1}`.
13//!
14//! `n = 3` is the first genuine **3-type object** the framework possesses (`K(A, 2)` was the first 2-type).
15
16use std::collections::{HashMap, HashSet};
17
18/// Order-preserving surjections `[m] ↠ [n]`, as nondecreasing length-`(m+1)` vectors hitting `0..=n`.
19fn surjections(m: usize, n: usize) -> Vec<Vec<u8>> {
20    fn rec(len: usize, n: u8, pos: usize, last: u8, cur: &mut Vec<u8>, out: &mut Vec<Vec<u8>>) {
21        if pos == len {
22            if (0..=n).all(|t| cur.contains(&t)) {
23                out.push(cur.clone());
24            }
25            return;
26        }
27        for v in last..=n {
28            cur.push(v);
29            rec(len, n, pos + 1, v, cur, out);
30            cur.pop();
31        }
32    }
33    let mut out = Vec::new();
34    rec(m + 1, n as u8, 0, 0, &mut Vec::new(), &mut out);
35    out
36}
37
38fn is_surjective(v: &[u8], n: usize) -> bool {
39    (0..=n as u8).all(|t| v.contains(&t))
40}
41
42fn drop_coord(v: &[u8], i: usize) -> Vec<u8> {
43    v.iter()
44        .enumerate()
45        .filter(|&(t, _)| t != i)
46        .map(|(_, &x)| x)
47        .collect()
48}
49
50/// Face map `dᵢ : Γ_m → Γ_{m-1}` of `K(A, n)` over `A = Z/modulus`. Basis surjection `σ ↦ σ∘δᵢ` when it
51/// stays surjective onto `[n]`, else `0` (the degree below is zero); collisions sum.
52fn face(modulus: usize, m: usize, n: usize, i: usize, x: &[usize]) -> Vec<usize> {
53    let sm = surjections(m, n);
54    let sm1 = surjections(m - 1, n);
55    let idx: HashMap<Vec<u8>, usize> = sm1
56        .iter()
57        .cloned()
58        .enumerate()
59        .map(|(k, v)| (v, k))
60        .collect();
61    let mut out = vec![0usize; sm1.len()];
62    for (k, sigma) in sm.iter().enumerate() {
63        let d = drop_coord(sigma, i);
64        if is_surjective(&d, n) {
65            let t = idx[&d];
66            out[t] = (out[t] + x[k]) % modulus;
67        }
68    }
69    out
70}
71
72/// Every degree-`m` simplex — all `A`-labelings of the surjections `[m] ↠ [n]`.
73fn gamma(modulus: usize, m: usize, n: usize) -> Vec<Vec<usize>> {
74    let size = surjections(m, n).len();
75    let mut out: Vec<Vec<usize>> = vec![vec![]];
76    for _ in 0..size {
77        let mut next = Vec::with_capacity(out.len() * modulus);
78        for t in &out {
79            for e in 0..modulus {
80                let mut u = t.clone();
81                u.push(e);
82                next.push(u);
83            }
84        }
85        out = next;
86    }
87    out
88}
89
90fn positions(m: usize, k: usize) -> Vec<usize> {
91    (0..=m).filter(|&i| i != k).collect()
92}
93
94/// `|ker hₖ|` at degree `m` — degree-`m` simplices whose faces `i ≠ k` are all zero. `> 1` ⟺ the horn
95/// `Λᵐ_k` fills non-uniquely (genuine cells in that degree).
96fn kernel_size(modulus: usize, m: usize, n: usize, k: usize) -> usize {
97    gamma(modulus, m, n)
98        .iter()
99        .filter(|y| {
100            positions(m, k)
101                .iter()
102                .all(|&p| face(modulus, m, n, p, y).iter().all(|&c| c == 0))
103        })
104        .count()
105}
106
107/// `|im hₖ|` at degree `m` — distinct face-tuples realized by some degree-`m` simplex.
108fn image_size(modulus: usize, m: usize, n: usize, k: usize) -> usize {
109    let mut images: HashSet<Vec<Vec<usize>>> = HashSet::new();
110    for y in gamma(modulus, m, n) {
111        images.insert(
112            positions(m, k)
113                .iter()
114                .map(|&p| face(modulus, m, n, p, &y))
115                .collect(),
116        );
117    }
118    images.len()
119}
120
121/// Number of **compatible horns** `Λᵐ_k` (tuples of degree-`(m-1)` simplices satisfying the simplicial
122/// identities `d_a x_b = d_{b-1} x_a`). `hₖ` is onto these iff the complex is Kan.
123fn compatible_horn_count(modulus: usize, m: usize, n: usize, k: usize) -> usize {
124    let pos = positions(m, k);
125    let lower = gamma(modulus, m - 1, n);
126    let base = lower.len();
127    let total: u128 = (base as u128).pow(pos.len() as u32);
128    let mut count = 0;
129    for idx in 0..total {
130        let mut x = idx;
131        let horn: HashMap<usize, Vec<usize>> = pos
132            .iter()
133            .map(|&p| {
134                let a = (x % base as u128) as usize;
135                x /= base as u128;
136                (p, lower[a].clone())
137            })
138            .collect();
139        let ok = pos.iter().enumerate().all(|(ai, &a)| {
140            pos[ai + 1..].iter().all(|&b| {
141                face(modulus, m - 1, n, a, &horn[&b]) == face(modulus, m - 1, n, b - 1, &horn[&a])
142            })
143        });
144        if ok {
145            count += 1;
146        }
147    }
148    count
149}
150
151/// **Extract** the homotopy group `π_k` of `K(A, n)` directly from the Kan complex, by horn-filling.
152/// This is the homotopy hypothesis realized computationally — given the ∞-groupoid *object*, read its
153/// homotopy back out. Returns `|π_k|`: `|A|` at `k = n`, trivial (`1`) everywhere else. (`K(A, n≥2)` is
154/// 1-connected, so `π_0 = π_1 = 1` by construction.)
155pub fn homotopy_group_size(modulus: usize, n: usize, k: usize) -> usize {
156    if k < 2 {
157        return 1;
158    }
159    kernel_size(modulus, k, n, 1)
160}
161
162/// Whether the Eilenberg–MacLane spaces `{K(A, n)}` form an **Ω-spectrum**: each is the loop space of
163/// the next, so the homotopy is invariant under the simultaneous shift `n ↦ n+1`, `k ↦ k+1`
164/// (`π_k(K(A,n)) = π_{k+1}(K(A,n+1))`). That deloopability is what makes the sequence a spectrum.
165pub fn is_omega_spectrum(modulus: usize, n_count: usize, k_range: usize) -> bool {
166    (2..(2 + n_count)).all(|n| {
167        (0..k_range).all(|k| {
168            homotopy_group_size(modulus, n, k) == homotopy_group_size(modulus, n + 1, k + 1)
169        })
170    })
171}
172
173/// The **stable homotopy** of the Eilenberg–MacLane spectrum `HA`: `π_k(HA) = colim_n π_{n+k}(K(A,n))`.
174/// For `HA` it is concentrated in degree `0` (`|A|` at `k = 0`, trivial elsewhere) — exactly what makes
175/// `HA` represent *ordinary* cohomology `Hⁿ(−; A)`. Read off the stable range (`N = 4`).
176pub fn stable_homotopy(modulus: usize, k: i32) -> usize {
177    // π_k(HA) = colim_n π_{n+k}(K(A,n)). For the EM spectrum the value is already stable at every n
178    // (π_{n+k}(K(A,n)) = A iff k = 0), so read it at n = 2 (the cheapest in-range representative).
179    let degree = 2 + k;
180    if degree < 0 {
181        return 1;
182    }
183    homotopy_group_size(modulus, 2, degree as usize)
184}
185
186/// The `k`-th **homology** `|H_k(K(A,n))|` via the normalized (Moore) chain complex: `N_k = ⋂_{i≥1} ker dᵢ`
187/// with differential `d_0`. Computed independently of the horn-filling homotopy extractor, so that their
188/// agreement is the genuine **Hurewicz** statement, not a tautology.
189pub fn homology_size(modulus: usize, n: usize, k: usize) -> usize {
190    if k < 2 {
191        return 1; // K(A, n≥2) is 1-connected: reduced H_0 = H_1 = 0
192    }
193    // cycles Z_k = degree-k simplices with ALL faces zero (in N_k and killed by d_0)
194    let z = gamma(modulus, k, n)
195        .iter()
196        .filter(|x| (0..=k).all(|i| face(modulus, k, n, i, x).iter().all(|&c| c == 0)))
197        .count();
198    // boundaries B_k = { d_0 y : y ∈ N_{k+1} } (y with faces 1..=k+1 zero)
199    let mut b: HashSet<Vec<usize>> = HashSet::new();
200    for y in gamma(modulus, k + 1, n) {
201        if (1..=(k + 1)).all(|i| face(modulus, k + 1, n, i, &y).iter().all(|&c| c == 0)) {
202            b.insert(face(modulus, k + 1, n, 0, &y));
203        }
204    }
205    z / b.len()
206}
207
208#[cfg(test)]
209#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/eilenberg_maclane/tests.rs"]
210mod tests;