Skip to main content

logicaffeine_proof/
two_group.rs

1//! The **2-group frontier** — climbing past `K(G,1)` to genuine 2-types, honestly.
2//!
3//! The tower named its 1-truncation: a *discrete* symmetry group `G` gives the ∞-groupoid
4//! `BG = K(G,1)` — `π₁ = G`, `πₙ = 0` for `n ≥ 2`. To populate `π₂` you need a **2-group** (a symmetry
5//! whose symmetries themselves have symmetries), modeled by a **crossed module** `∂: H → G`:
6//!
7//! - `π₁ = coker(∂) = G / ∂(H)` — the symmetries that survive modulo the higher cells, and
8//! - `π₂ = ker(∂)` — the genuinely higher homotopy.
9//!
10//! This module builds that machinery and is honest about where our SAT structure sits in it: our
11//! symmetry is the *degenerate* crossed module `1 → G` (so `π₂ = 0`, `BG = K(G,1)`), and a genuine
12//! 2-group `Z/m → 1` gives `π₂ = Z/m ≠ 0` — a `K(Z/m, 2)`. The machinery reads off both; our case is
13//! the 1-type. Climbing further (`π₃, …`) is the same construction one categorical level up — the
14//! frontier, named, not claimed.
15
16/// A finite group by its (0-indexed) multiplication table.
17#[derive(Clone)]
18pub struct FiniteGroup {
19    /// `mul[a][b] = a · b`.
20    pub mul: Vec<Vec<usize>>,
21    /// The identity element.
22    pub id: usize,
23}
24
25impl FiniteGroup {
26    pub fn order(&self) -> usize {
27        self.mul.len()
28    }
29
30    pub fn inverse(&self, a: usize) -> usize {
31        (0..self.order())
32            .find(|&b| self.mul[a][b] == self.id)
33            .expect("a group element has an inverse")
34    }
35
36    /// The trivial group `1`.
37    pub fn trivial() -> FiniteGroup {
38        FiniteGroup {
39            mul: vec![vec![0]],
40            id: 0,
41        }
42    }
43
44    /// The cyclic group `Z/m` (elements `0..m`, addition mod `m`).
45    pub fn cyclic(m: usize) -> FiniteGroup {
46        let mul = (0..m)
47            .map(|a| (0..m).map(|b| (a + b) % m).collect())
48            .collect();
49        FiniteGroup { mul, id: 0 }
50    }
51
52    /// The symmetric group `S_n` (all `n!` permutations, indexed; multiplication = composition). This
53    /// is the shape of a pigeonhole symmetry group (pigeon/hole permutations).
54    pub fn symmetric(n: usize) -> FiniteGroup {
55        // enumerate permutations of 0..n (Heap-free: lexicographic via Steinhaus–Johnson or simple
56        // recursive build)
57        let mut perms: Vec<Vec<usize>> = Vec::new();
58        let mut cur: Vec<usize> = (0..n).collect();
59        permute(&mut cur, 0, &mut perms);
60        let index: std::collections::HashMap<Vec<usize>, usize> = perms
61            .iter()
62            .cloned()
63            .enumerate()
64            .map(|(i, p)| (p, i))
65            .collect();
66        let compose =
67            |p: &[usize], q: &[usize]| -> Vec<usize> { (0..n).map(|i| p[q[i]]).collect() };
68        let mul: Vec<Vec<usize>> = perms
69            .iter()
70            .map(|p| perms.iter().map(|q| index[&compose(p, q)]).collect())
71            .collect();
72        let id = index[&(0..n).collect::<Vec<_>>()];
73        FiniteGroup { mul, id }
74    }
75}
76
77fn permute(arr: &mut Vec<usize>, k: usize, out: &mut Vec<Vec<usize>>) {
78    if k == arr.len() {
79        out.push(arr.clone());
80        return;
81    }
82    for i in k..arr.len() {
83        arr.swap(k, i);
84        permute(arr, k + 1, out);
85        arr.swap(k, i);
86    }
87}
88
89/// A **crossed module** `∂: H → G` — the algebraic model of a 2-group. `partial[h]` is `∂(h) ∈ G`,
90/// a group homomorphism. Its homotopy groups are `π₁ = coker(∂)` and `π₂ = ker(∂)`.
91pub struct CrossedModule {
92    pub g: FiniteGroup,
93    pub h: FiniteGroup,
94    /// `partial[x] = ∂(x)` for `x ∈ H`.
95    pub partial: Vec<usize>,
96}
97
98impl CrossedModule {
99    /// `∂` must be a group homomorphism: `∂(x · y) = ∂(x) · ∂(y)`.
100    pub fn is_homomorphism(&self) -> bool {
101        (0..self.h.order()).all(|x| {
102            (0..self.h.order()).all(|y| {
103                self.partial[self.h.mul[x][y]] == self.g.mul[self.partial[x]][self.partial[y]]
104            })
105        })
106    }
107
108    /// `π₂ = ker(∂)` — the elements of `H` mapping to the identity of `G`. The genuine higher homotopy.
109    pub fn pi_two(&self) -> Vec<usize> {
110        (0..self.h.order())
111            .filter(|&x| self.partial[x] == self.g.id)
112            .collect()
113    }
114
115    /// `|im(∂)|` — the size of `∂`'s image in `G`.
116    pub fn image_size(&self) -> usize {
117        let mut img: Vec<usize> = (0..self.h.order()).map(|x| self.partial[x]).collect();
118        img.sort_unstable();
119        img.dedup();
120        img.len()
121    }
122
123    /// `|π₁| = |coker(∂)| = |G| / |im(∂)|` (valid when `im(∂)` is normal, which holds for our examples).
124    pub fn pi_one_order(&self) -> usize {
125        self.g.order() / self.image_size()
126    }
127}
128
129#[cfg(test)]
130#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/two_group/tests.rs"]
131mod tests;