Skip to main content

logicaffeine_proof/
cubical.rs

1//! A general **`d`-dimensional cubical-homology engine** — one engine, every rung of the ladder.
2//!
3//! `progress_complex` produced `π₁` (2 processes) and `π₂` (3 processes) with hand-built 2D and 3D
4//! complexes. Rather than write a 4D one, then a 5D one, this is the lift: a single cubical complex in
5//! *any* dimension, computing the full Betti vector `(β₀, β₁, …, β_d)` over `GF(2)`. Then the ladder is
6//! literal — **`d` processes → a `(d−1)`-sphere void → `π_{d−1}` ≠ 0** — and walking it toward the
7//! `∞`-groupoid is just "one more process, one more dimension," handled by the same code.
8//!
9//! An elementary cube is a [`Cube`]: a minimal corner plus the set of free axes it extends along (its
10//! dimension). Its boundary is the `2k` faces obtained by pinning each free axis low or high. From a set
11//! of filled top cells we take the downward closure, build the boundary matrices `∂_k`, and read
12//! `β_k = #C_k − rank ∂_k − rank ∂_{k+1}` — homology with no shortcuts, in arbitrary dimension.
13
14use crate::progress_complex::gf2_rank_wide;
15use std::collections::{BTreeSet, HashMap};
16
17/// An elementary cube: the minimal corner, and the sorted set of axes it extends along (each by one
18/// unit). The dimension is the number of free axes; fixed axes hold the corner's value.
19#[derive(Clone, PartialEq, Eq, Hash, PartialOrd, Ord, Debug)]
20pub struct Cube {
21    pub corner: Vec<usize>,
22    pub dirs: Vec<usize>,
23}
24
25impl Cube {
26    pub fn dim(&self) -> usize {
27        self.dirs.len()
28    }
29
30    /// The `2k` boundary faces — for each free axis, the lower face (pin it at the corner) and the upper
31    /// face (pin it at corner + 1). Over `GF(2)` the boundary is their unsigned sum.
32    pub fn boundary(&self) -> Vec<Cube> {
33        let mut faces = Vec::with_capacity(2 * self.dirs.len());
34        for (idx, &a) in self.dirs.iter().enumerate() {
35            let mut sub = self.dirs.clone();
36            sub.remove(idx);
37            faces.push(Cube {
38                corner: self.corner.clone(),
39                dirs: sub.clone(),
40            });
41            let mut up = self.corner.clone();
42            up[a] += 1;
43            faces.push(Cube {
44                corner: up,
45                dirs: sub,
46            });
47        }
48        faces
49    }
50}
51
52/// A cubical complex, stored as the cells of each dimension `0..=dim`.
53pub struct CubicalComplex {
54    cells: Vec<BTreeSet<Cube>>,
55    dim: usize,
56}
57
58impl CubicalComplex {
59    /// Build from filled top-dimensional cells, taking the downward closure (all faces of all faces).
60    pub fn from_top_cells(top: Vec<Cube>) -> Self {
61        let dim = top.iter().map(Cube::dim).max().unwrap_or(0);
62        let mut cells: Vec<BTreeSet<Cube>> = vec![BTreeSet::new(); dim + 1];
63        for c in top {
64            let d = c.dim();
65            cells[d].insert(c);
66        }
67        for k in (1..=dim).rev() {
68            let current: Vec<Cube> = cells[k].iter().cloned().collect();
69            for c in current {
70                for f in c.boundary() {
71                    cells[f.dim()].insert(f);
72                }
73            }
74        }
75        CubicalComplex { cells, dim }
76    }
77
78    /// The progress complex of `d` processes with the given step `lengths`: every grid `d`-cell is
79    /// filled, except those in `forbidden` (the mutual-exclusion / synchronization region).
80    pub fn progress(lengths: &[usize], forbidden: &[Vec<usize>]) -> Self {
81        let d = lengths.len();
82        let forbidden: BTreeSet<Vec<usize>> = forbidden.iter().cloned().collect();
83        let mut top = Vec::new();
84        let mut idx = vec![0usize; d];
85        loop {
86            if !forbidden.contains(&idx) {
87                top.push(Cube {
88                    corner: idx.clone(),
89                    dirs: (0..d).collect(),
90                });
91            }
92            let mut a = 0;
93            while a < d {
94                idx[a] += 1;
95                if idx[a] < lengths[a] {
96                    break;
97                }
98                idx[a] = 0;
99                a += 1;
100            }
101            if a == d {
102                break;
103            }
104        }
105        CubicalComplex::from_top_cells(top)
106    }
107
108    pub fn dim(&self) -> usize {
109        self.dim
110    }
111
112    pub fn num_cells(&self, k: usize) -> usize {
113        self.cells.get(k).map_or(0, BTreeSet::len)
114    }
115
116    /// `rank ∂_k` over `GF(2)` — the boundary map from `k`-cells to `(k−1)`-cells.
117    fn boundary_rank(&self, k: usize) -> usize {
118        if k == 0 || k > self.dim {
119            return 0;
120        }
121        let lower: Vec<Cube> = self.cells[k - 1].iter().cloned().collect();
122        let ncols = lower.len();
123        if ncols == 0 {
124            return 0;
125        }
126        let lidx: HashMap<Cube, usize> =
127            lower.into_iter().enumerate().map(|(i, c)| (c, i)).collect();
128        let rows: Vec<Vec<u64>> = self.cells[k]
129            .iter()
130            .map(|c| {
131                let mut row = vec![0u64; ncols.div_ceil(64)];
132                for f in c.boundary() {
133                    let idx = lidx[&f];
134                    row[idx / 64] ^= 1u64 << (idx % 64);
135                }
136                row
137            })
138            .collect();
139        gf2_rank_wide(rows, ncols)
140    }
141
142    /// The Betti vector `(β₀, …, β_d)`: `β_k = #C_k − rank ∂_k − rank ∂_{k+1}` over `GF(2)`.
143    pub fn betti(&self) -> Vec<usize> {
144        let mut ranks = vec![0usize; self.dim + 2];
145        for k in 1..=self.dim {
146            ranks[k] = self.boundary_rank(k);
147        }
148        (0..=self.dim)
149            .map(|k| self.cells[k].len() - ranks[k] - ranks[k + 1])
150            .collect()
151    }
152
153    /// `χ = Σ (−1)^k #C_k` — the alternating cell count, equal to `Σ (−1)^k β_k` (Euler–Poincaré).
154    pub fn euler(&self) -> i64 {
155        (0..=self.dim)
156            .map(|k| {
157                let c = self.cells[k].len() as i64;
158                if k % 2 == 0 {
159                    c
160                } else {
161                    -c
162                }
163            })
164            .sum()
165    }
166}
167
168#[cfg(test)]
169#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/cubical/tests.rs"]
170mod tests;