Skip to main content

logicaffeine_proof/
progress_complex.rs

1//! **Genuine higher homotopy, at last** — `π₁ ≠ 0` from real concurrency, the hole *is* the deadlock.
2//!
3//! Everything below `proof_rewrite` was a 1-type or contractible: a *discrete* symmetry gives `K(G,1)`,
4//! a *deterministic* trace gives a contractible cube complex. Genuine non-trivial homotopy needs a
5//! **forbidden region** — and concurrency with shared resources is exactly where one appears
6//! (Fajstrup–Goubault–Raussen, *directed algebraic topology*).
7//!
8//! Model two processes of lengths `n` and `m` by their **progress complex**: a grid of states `(i, j)`
9//! ("`P` has run `i` steps, `Q` has run `j` steps"), unit edges for single steps, and a filled square
10//! at every cell where the two steps commute — *except* cells in the **forbidden region** (both
11//! processes inside their critical section at once, which mutual exclusion forbids). Removing those
12//! cells leaves a **hole**, and the hole is not decoration: it is the synchronization obstruction,
13//! the deadlock, made into topology.
14//!
15//! We compute the homology rigorously — `β₀` by union-find, `β₁ = #E − #V + β₀ − rank ∂₂` and
16//! `β₂ = #C − rank ∂₂` with the boundary rank taken over `GF(2)` by Gaussian elimination — and we
17//! cross-check every case against the Euler–Poincaré identity `β₀ − β₁ + β₂ = χ`. No contention gives
18//! a contractible square (`β₁ = 0`, determinism). One mutex gives `β₁ = 1`: the execution space is a
19//! circle, and the two directed ways around the hole (`P`-first vs `Q`-first) are genuinely
20//! inequivalent schedules — **the hole is precisely where the scheduler symmetry can no longer be
21//! broken to one canonical class.** Higher homotopy = the obstruction to symmetry breaking.
22
23use std::collections::{BTreeSet, HashMap};
24
25/// `GF(2)` rank of a set of rows (each a bitset of column indices) by Gaussian elimination.
26fn gf2_rank(mut rows: Vec<u128>) -> usize {
27    let mut rank = 0;
28    let mut col = 0;
29    while col < 128 && rank < rows.len() {
30        let bit = 1u128 << col;
31        if let Some(pivot) = (rank..rows.len()).find(|&r| rows[r] & bit != 0) {
32            rows.swap(rank, pivot);
33            let pr = rows[rank];
34            for r in 0..rows.len() {
35                if r != rank && rows[r] & bit != 0 {
36                    rows[r] ^= pr;
37                }
38            }
39            rank += 1;
40        }
41        col += 1;
42    }
43    rank
44}
45
46/// `GF(2)` rank for wide bitsets (more than 128 columns), each row a `Vec<u64>` of `words` limbs.
47pub(crate) fn gf2_rank_wide(mut rows: Vec<Vec<u64>>, ncols: usize) -> usize {
48    let words = ncols.div_ceil(64);
49    for r in &mut rows {
50        r.resize(words, 0);
51    }
52    let mut rank = 0;
53    for col in 0..ncols {
54        let (w, bit) = (col / 64, 1u64 << (col % 64));
55        if let Some(pivot) = (rank..rows.len()).find(|&r| rows[r][w] & bit != 0) {
56            rows.swap(rank, pivot);
57            let pr = rows[rank].clone();
58            for r in 0..rows.len() {
59                if r != rank && rows[r][w] & bit != 0 {
60                    for t in 0..words {
61                        rows[r][t] ^= pr[t];
62                    }
63                }
64            }
65            rank += 1;
66            if rank == rows.len() {
67                break;
68            }
69        }
70    }
71    rank
72}
73
74/// The progress complex of two processes of lengths `n`, `m` (an `n × m` grid of cells), with a set of
75/// **forbidden cells** (the mutual-exclusion region) left unfilled.
76pub struct ProgressComplex {
77    pub n: usize,
78    pub m: usize,
79    forbidden: BTreeSet<(usize, usize)>,
80}
81
82impl ProgressComplex {
83    pub fn new(n: usize, m: usize, forbidden: &[(usize, usize)]) -> Self {
84        ProgressComplex {
85            n,
86            m,
87            forbidden: forbidden.iter().copied().collect(),
88        }
89    }
90
91    fn vid(&self, i: usize, j: usize) -> usize {
92        i * (self.m + 1) + j
93    }
94
95    /// The four boundary edges of cell `(i, j)`, each as an ordered vertex-id pair.
96    fn cell_edges(&self, i: usize, j: usize) -> [(usize, usize); 4] {
97        let v = |a: usize, b: usize| self.vid(a, b);
98        let order = |a: usize, b: usize| (a.min(b), a.max(b));
99        [
100            order(v(i, j), v(i + 1, j)),         // bottom
101            order(v(i, j + 1), v(i + 1, j + 1)), // top
102            order(v(i, j), v(i, j + 1)),         // left
103            order(v(i + 1, j), v(i + 1, j + 1)), // right
104        ]
105    }
106
107    fn allowed_cells(&self) -> Vec<(usize, usize)> {
108        let mut cells = Vec::new();
109        for i in 0..self.n {
110            for j in 0..self.m {
111                if !self.forbidden.contains(&(i, j)) {
112                    cells.push((i, j));
113                }
114            }
115        }
116        cells
117    }
118
119    /// The Betti numbers `(β₀, β₁, β₂)` of the **closure of the allowed cells** — vertices and edges are
120    /// included exactly when they bound some allowed cell, so removing a forbidden region opens a real
121    /// hole. Homology over `GF(2)`, fully computed (no shortcuts).
122    pub fn betti(&self) -> (usize, usize, usize) {
123        let cells = self.allowed_cells();
124
125        let mut edge_set: BTreeSet<(usize, usize)> = BTreeSet::new();
126        let mut vert_set: BTreeSet<usize> = BTreeSet::new();
127        for &(i, j) in &cells {
128            for e in self.cell_edges(i, j) {
129                edge_set.insert(e);
130                vert_set.insert(e.0);
131                vert_set.insert(e.1);
132            }
133        }
134
135        let edges: Vec<(usize, usize)> = edge_set.into_iter().collect();
136        let edge_index: HashMap<(usize, usize), usize> =
137            edges.iter().enumerate().map(|(k, &e)| (e, k)).collect();
138        let verts: Vec<usize> = vert_set.into_iter().collect();
139        let vert_index: HashMap<usize, usize> =
140            verts.iter().enumerate().map(|(k, &v)| (v, k)).collect();
141        let (nv, ne, nc) = (verts.len(), edges.len(), cells.len());
142        assert!(
143            ne <= 128,
144            "GF(2) rows are u128 — keep grids small (#edges = {ne})"
145        );
146
147        // β₀ — connected components of the 1-skeleton by union-find.
148        let mut parent: Vec<usize> = (0..nv).collect();
149        fn find(parent: &mut [usize], x: usize) -> usize {
150            let mut r = x;
151            while parent[r] != r {
152                r = parent[r];
153            }
154            let mut c = x;
155            while parent[c] != r {
156                let nx = parent[c];
157                parent[c] = r;
158                c = nx;
159            }
160            r
161        }
162        for &(a, b) in &edges {
163            let (ra, rb) = (
164                find(&mut parent, vert_index[&a]),
165                find(&mut parent, vert_index[&b]),
166            );
167            if ra != rb {
168                parent[ra] = rb;
169            }
170        }
171        let b0 = (0..nv).filter(|&x| find(&mut parent, x) == x).count();
172
173        // ∂₂ over GF(2): each allowed cell ↦ the bitset of its four boundary edges.
174        let d2: Vec<u128> = cells
175            .iter()
176            .map(|&(i, j)| {
177                self.cell_edges(i, j)
178                    .iter()
179                    .fold(0u128, |row, e| row ^ (1u128 << edge_index[e]))
180            })
181            .collect();
182        let rank2 = gf2_rank(d2);
183
184        let b2 = nc - rank2;
185        // β₁ = dim Z₁ − dim B₁ = (#E − rank ∂₁) − rank ∂₂, with rank ∂₁ = #V − β₀.
186        let b1 = ne + b0 - nv - rank2;
187        (b0, b1, b2)
188    }
189
190    /// `χ = #V − #E + #C` over the closure of the allowed cells.
191    pub fn euler(&self) -> i64 {
192        let cells = self.allowed_cells();
193        let mut edge_set: BTreeSet<(usize, usize)> = BTreeSet::new();
194        let mut vert_set: BTreeSet<usize> = BTreeSet::new();
195        for &(i, j) in &cells {
196            for e in self.cell_edges(i, j) {
197                edge_set.insert(e);
198                vert_set.insert(e.0);
199                vert_set.insert(e.1);
200            }
201        }
202        vert_set.len() as i64 - edge_set.len() as i64 + cells.len() as i64
203    }
204}
205
206/// A 3D coordinate (vertex) of the three-process progress complex.
207type V3 = (usize, usize, usize);
208
209/// The progress complex of **three** processes of lengths `n`, `m`, `p` — a 3D grid of states, filled
210/// with solid 3-cells (cubes) where all three steps commute, *except* forbidden cells. Climbing one
211/// homotopy dimension: a forbidden core now leaves a hollow **2-sphere**, so `β₂ = π₂ ≠ 0` — the first
212/// genuine `π₂` the tower *produces* (not just admits). Adding a process climbs a rung; the limit of
213/// "one more process, one more dimension" is the `∞`-groupoid the ladder points at.
214pub struct ProgressComplex3 {
215    pub n: usize,
216    pub m: usize,
217    pub p: usize,
218    forbidden: BTreeSet<V3>,
219}
220
221impl ProgressComplex3 {
222    pub fn new(n: usize, m: usize, p: usize, forbidden: &[V3]) -> Self {
223        ProgressComplex3 {
224            n,
225            m,
226            p,
227            forbidden: forbidden.iter().copied().collect(),
228        }
229    }
230
231    /// The eight corners of cell `(i, j, l)`.
232    fn corners(i: usize, j: usize, l: usize) -> [V3; 8] {
233        let mut c = [(0, 0, 0); 8];
234        for (b, slot) in c.iter_mut().enumerate() {
235            *slot = (i + (b & 1), j + ((b >> 1) & 1), l + ((b >> 2) & 1));
236        }
237        c
238    }
239
240    fn differ_in_one(a: V3, b: V3) -> bool {
241        let d = (a.0 != b.0) as u8 + (a.1 != b.1) as u8 + (a.2 != b.2) as u8;
242        d == 1
243    }
244
245    /// The twelve edges of a cell — corner pairs differing in exactly one coordinate.
246    fn cell_edges(i: usize, j: usize, l: usize) -> Vec<[V3; 2]> {
247        let cs = Self::corners(i, j, l);
248        let mut es = Vec::new();
249        for a in 0..8 {
250            for b in (a + 1)..8 {
251                if Self::differ_in_one(cs[a], cs[b]) {
252                    let (mut u, mut v) = (cs[a], cs[b]);
253                    if v < u {
254                        std::mem::swap(&mut u, &mut v);
255                    }
256                    es.push([u, v]);
257                }
258            }
259        }
260        es
261    }
262
263    /// The six faces of a cell, each the four corners sharing one fixed coordinate (axis, value), sorted.
264    fn cell_faces(i: usize, j: usize, l: usize) -> Vec<[V3; 4]> {
265        let cs = Self::corners(i, j, l);
266        let mut fs = Vec::new();
267        for axis in 0..3 {
268            for val in 0..2 {
269                let mut quad: Vec<V3> = cs
270                    .iter()
271                    .copied()
272                    .filter(|&c| [c.0, c.1, c.2][axis] == [i, j, l][axis] + val)
273                    .collect();
274                quad.sort_unstable();
275                fs.push([quad[0], quad[1], quad[2], quad[3]]);
276            }
277        }
278        fs
279    }
280
281    /// The four boundary edges of a face (its four corners, adjacent pairs).
282    fn face_edges(face: &[V3; 4]) -> Vec<[V3; 2]> {
283        let mut es = Vec::new();
284        for a in 0..4 {
285            for b in (a + 1)..4 {
286                if Self::differ_in_one(face[a], face[b]) {
287                    let (mut u, mut v) = (face[a], face[b]);
288                    if v < u {
289                        std::mem::swap(&mut u, &mut v);
290                    }
291                    es.push([u, v]);
292                }
293            }
294        }
295        es
296    }
297
298    fn allowed_cells(&self) -> Vec<V3> {
299        let mut cells = Vec::new();
300        for i in 0..self.n {
301            for j in 0..self.m {
302                for l in 0..self.p {
303                    if !self.forbidden.contains(&(i, j, l)) {
304                        cells.push((i, j, l));
305                    }
306                }
307            }
308        }
309        cells
310    }
311
312    /// Betti numbers `(β₀, β₁, β₂, β₃)` of the closure of the allowed 3-cells — full `GF(2)` homology
313    /// through `∂₃`. `β₂` is the genuine `π₂` (2-voids); `β₃` detects enclosed 3-voids (none here).
314    pub fn betti(&self) -> (usize, usize, usize, usize) {
315        let cells = self.allowed_cells();
316
317        // collect closure: every vertex/edge/face that bounds an allowed 3-cell
318        let mut verts: BTreeSet<V3> = BTreeSet::new();
319        let mut edges: BTreeSet<[V3; 2]> = BTreeSet::new();
320        let mut faces: BTreeSet<[V3; 4]> = BTreeSet::new();
321        for &(i, j, l) in &cells {
322            for c in Self::corners(i, j, l) {
323                verts.insert(c);
324            }
325            for e in Self::cell_edges(i, j, l) {
326                edges.insert(e);
327            }
328            for f in Self::cell_faces(i, j, l) {
329                faces.insert(f);
330            }
331        }
332        let verts: Vec<V3> = verts.into_iter().collect();
333        let edges: Vec<[V3; 2]> = edges.into_iter().collect();
334        let faces: Vec<[V3; 4]> = faces.into_iter().collect();
335        let vidx: HashMap<V3, usize> = verts.iter().enumerate().map(|(k, &v)| (v, k)).collect();
336        let eidx: HashMap<[V3; 2], usize> =
337            edges.iter().enumerate().map(|(k, &e)| (e, k)).collect();
338        let fidx: HashMap<[V3; 4], usize> =
339            faces.iter().enumerate().map(|(k, &f)| (f, k)).collect();
340        let (nv, ne, nf, nc) = (verts.len(), edges.len(), faces.len(), cells.len());
341
342        // β₀ — components of the 1-skeleton.
343        let mut parent: Vec<usize> = (0..nv).collect();
344        fn find(parent: &mut [usize], x: usize) -> usize {
345            let mut r = x;
346            while parent[r] != r {
347                r = parent[r];
348            }
349            let mut c = x;
350            while parent[c] != r {
351                let nx = parent[c];
352                parent[c] = r;
353                c = nx;
354            }
355            r
356        }
357        for e in &edges {
358            let (ra, rb) = (
359                find(&mut parent, vidx[&e[0]]),
360                find(&mut parent, vidx[&e[1]]),
361            );
362            if ra != rb {
363                parent[ra] = rb;
364            }
365        }
366        let b0 = (0..nv).filter(|&x| find(&mut parent, x) == x).count();
367
368        // ∂₂ : faces → edges (4 each), ∂₃ : cells → faces (6 each), ranks over GF(2).
369        let d2: Vec<Vec<u64>> = faces
370            .iter()
371            .map(|f| {
372                let mut row = vec![0u64; ne.div_ceil(64)];
373                for e in Self::face_edges(f) {
374                    let idx = eidx[&e];
375                    row[idx / 64] ^= 1u64 << (idx % 64);
376                }
377                row
378            })
379            .collect();
380        let d3: Vec<Vec<u64>> = cells
381            .iter()
382            .map(|&(i, j, l)| {
383                let mut row = vec![0u64; nf.div_ceil(64)];
384                for f in Self::cell_faces(i, j, l) {
385                    let idx = fidx[&f];
386                    row[idx / 64] ^= 1u64 << (idx % 64);
387                }
388                row
389            })
390            .collect();
391        let rank2 = gf2_rank_wide(d2, ne);
392        let rank3 = gf2_rank_wide(d3, nf);
393
394        let b1 = ne + b0 - nv - rank2;
395        let b2 = nf - rank2 - rank3;
396        let b3 = nc - rank3;
397        (b0, b1, b2, b3)
398    }
399}
400
401#[cfg(test)]
402#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/progress_complex/tests.rs"]
403mod tests;