logicaffeine_proof/two_type.rs
1//! A genuinely **2-truncated** ∞-groupoid, had as an object: the minimal `K(A, 2)`.
2//!
3//! `kan_complex` built the nerve `BG = K(G, 1)` and proved it 1-truncated (inner horns fill *uniquely*).
4//! This is the first object *beyond* that — a Kan complex with real `π₂ ≠ 0` living inside it, not merely
5//! admitted by a crossed module or glimpsed as homology. It is the Eilenberg–MacLane space `K(A, 2)`:
6//! `π₂ = A`, every other `πₙ = 0`.
7//!
8//! The model is Dold–Kan `Γ(A[2])` for the chain complex with `A` in degree 2. Its `n`-simplices are the
9//! `A`-linear combinations of order-preserving **surjections `[n] ↠ [2]`** (since the complex is
10//! concentrated in degree 2, a face that fails to stay surjective dies — `C₁ = C₃ = 0`). Concretely an
11//! `n`-simplex is an `A`-labeling of `S_n = {surjections [n] ↠ [2]}`, and `dᵢ` pulls back along the
12//! `i`-th coface, keeping only the still-surjective terms. It is a simplicial *abelian group*, hence
13//! automatically a Kan complex — and we verify, by enumeration:
14//!
15//! - **`π₂ ≠ 0`**: the inner horn `Λ²₁` has `|A|` fillers (the `2`-cells), *not* the unique filler of a
16//! 1-type. This is the structure `K(G,1)` provably lacked.
17//! - **Kan**: every horn fills (the face-tuple map onto the compatible-horn object is surjective), checked
18//! in degrees 2, 3, 4.
19//! - **exactly 2-truncated**: degree-4 inner horns fill *uniquely* again (no `π₃`), so the higher homotopy
20//! stops at level 2.
21
22use std::collections::{HashMap, HashSet};
23
24/// All order-preserving surjections `[n] ↠ [2]`, as nondecreasing length-`(n+1)` value vectors hitting
25/// `0, 1, 2`. `S_n` — the basis of the degree-`n` part. Empty for `n < 2` (so `Γ₀ = Γ₁ = 0`).
26fn surjections(n: usize) -> Vec<Vec<u8>> {
27 fn rec(len: usize, pos: usize, last: u8, cur: &mut Vec<u8>, out: &mut Vec<Vec<u8>>) {
28 if pos == len {
29 if cur.contains(&0) && cur.contains(&1) && cur.contains(&2) {
30 out.push(cur.clone());
31 }
32 return;
33 }
34 for v in last..=2 {
35 cur.push(v);
36 rec(len, pos + 1, v, cur, out);
37 cur.pop();
38 }
39 }
40 let mut out = Vec::new();
41 rec(n + 1, 0, 0, &mut Vec::new(), &mut out);
42 out
43}
44
45fn is_surjective(v: &[u8]) -> bool {
46 v.contains(&0) && v.contains(&1) && v.contains(&2)
47}
48
49/// `σ ∘ δᵢ` — precompose a surjection with the `i`-th coface, i.e. drop coordinate `i`.
50fn drop_coord(v: &[u8], i: usize) -> Vec<u8> {
51 v.iter()
52 .enumerate()
53 .filter(|&(t, _)| t != i)
54 .map(|(_, &x)| x)
55 .collect()
56}
57
58/// The face map `dᵢ : Γ_n → Γ_{n-1}` over `A = Z/modulus`. A degree-`n` simplex is an `A`-labeling of
59/// `S_n`; `dᵢ` sends basis `σ` to `σ∘δᵢ` when that stays surjective, else to `0`, summing collisions.
60fn face(modulus: usize, n: usize, i: usize, x: &[usize]) -> Vec<usize> {
61 let sn = surjections(n);
62 let sn1 = surjections(n - 1);
63 let idx: HashMap<Vec<u8>, usize> = sn1
64 .iter()
65 .cloned()
66 .enumerate()
67 .map(|(k, v)| (v, k))
68 .collect();
69 let mut out = vec![0usize; sn1.len()];
70 for (k, sigma) in sn.iter().enumerate() {
71 let d = drop_coord(sigma, i);
72 if is_surjective(&d) {
73 let t = idx[&d];
74 out[t] = (out[t] + x[k]) % modulus;
75 }
76 }
77 out
78}
79
80/// Every degree-`n` simplex — all `A`-labelings of `S_n` (`|A|^{|S_n|}` of them).
81fn gamma(modulus: usize, n: usize) -> Vec<Vec<usize>> {
82 let size = surjections(n).len();
83 let mut out: Vec<Vec<usize>> = vec![vec![]];
84 for _ in 0..size {
85 let mut next = Vec::with_capacity(out.len() * modulus);
86 for t in &out {
87 for e in 0..modulus {
88 let mut u = t.clone();
89 u.push(e);
90 next.push(u);
91 }
92 }
93 out = next;
94 }
95 out
96}
97
98fn positions(n: usize, k: usize) -> Vec<usize> {
99 (0..=n).filter(|&i| i != k).collect()
100}
101
102/// The number of degree-`n` simplices filling the horn `Λⁿ_k` whose given faces are all the chosen
103/// `horn[i]` (`i ≠ k`).
104fn filler_count(modulus: usize, n: usize, k: usize, horn: &HashMap<usize, Vec<usize>>) -> usize {
105 gamma(modulus, n)
106 .iter()
107 .filter(|y| {
108 positions(n, k)
109 .iter()
110 .all(|&p| &face(modulus, n, p, y) == &horn[&p])
111 })
112 .count()
113}
114
115/// `|ker hₖ|` — degree-`n` simplices whose faces `i ≠ k` are all zero. Equals the number of fillers of
116/// the *trivial* horn; `> 1` means a horn fills non-uniquely (genuine higher cells in that degree).
117fn kernel_size(modulus: usize, n: usize, k: usize) -> usize {
118 gamma(modulus, n)
119 .iter()
120 .filter(|y| {
121 positions(n, k)
122 .iter()
123 .all(|&p| face(modulus, n, p, y).iter().all(|&c| c == 0))
124 })
125 .count()
126}
127
128/// `|im hₖ|` — the number of distinct face-tuples `(dᵢ y)_{i≠k}` realized by some degree-`n` simplex.
129fn image_size(modulus: usize, n: usize, k: usize) -> usize {
130 let mut images: HashSet<Vec<Vec<usize>>> = HashSet::new();
131 for y in gamma(modulus, n) {
132 images.insert(
133 positions(n, k)
134 .iter()
135 .map(|&p| face(modulus, n, p, &y))
136 .collect(),
137 );
138 }
139 images.len()
140}
141
142/// The number of **compatible horns** `Λⁿ_k`: tuples `(x_i)_{i≠k}` of degree-`(n-1)` simplices satisfying
143/// the simplicial identities `d_a x_b = d_{b-1} x_a` (`a < b`). The horn maps `hₖ` is onto these iff Kan.
144fn compatible_horn_count(modulus: usize, n: usize, k: usize) -> usize {
145 let pos = positions(n, k);
146 let lower = gamma(modulus, n - 1);
147 let base = lower.len();
148 let total: u128 = (base as u128).pow(pos.len() as u32);
149 let mut count = 0;
150 for idx in 0..total {
151 let mut x = idx;
152 let horn: HashMap<usize, Vec<usize>> = pos
153 .iter()
154 .map(|&p| {
155 let a = (x % base as u128) as usize;
156 x /= base as u128;
157 (p, lower[a].clone())
158 })
159 .collect();
160 // simplicial identity d_a x_b = d_{b-1} x_a for every pair a < b of given positions
161 let ok = pos.iter().enumerate().all(|(ai, &a)| {
162 pos[ai + 1..].iter().all(|&b| {
163 face(modulus, n - 1, a, &horn[&b]) == face(modulus, n - 1, b - 1, &horn[&a])
164 })
165 });
166 if ok {
167 count += 1;
168 }
169 }
170 count
171}
172
173#[cfg(test)]
174#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/two_type/tests.rs"]
175mod tests;