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;