Skip to main content

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;