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;