Skip to main content

logicaffeine_proof/
groupoid.rs

1//! The **action groupoid** — what symmetry breaking *means*, categorically, as checked code.
2//!
3//! Symmetry breaking is not a heuristic; it is the computation of `π₀` of a groupoid. A symmetry
4//! group `G` acts on the space `X` of assignments (the "possible worlds"). The **action groupoid**
5//! `X ⫽ G` has the assignments as objects and the group elements as the (iso)morphisms `α → g·α`:
6//! two assignments are *isomorphic* iff related by a symmetry — bisimilar worlds. Symmetry breaking
7//! keeps ONE assignment per isomorphism class — it computes the **skeleton**, equivalently
8//! `π₀(X ⫽ G)` (the set of orbits = connected components). The exponential→polynomial collapse is
9//! exactly `|X| → |π₀(X ⫽ G)|`.
10//!
11//! This `X ⫽ G` is a **1-groupoid** (h-level 3 in the homotopy-level table). The ∞-tower above it —
12//! symmetries *between* symmetry-breakings, then between those, … — is the honest open direction. We
13//! build the first rung (this 1-groupoid) solidly and *check* that symmetry breaking is its `π₀`; the
14//! next rung (a groupoid of measures-and-their-morphisms) is sketched in the campaign notes. We do
15//! not claim to have built an ∞-groupoid — only the 1-truncation that the present theory occupies,
16//! and the precise statement of what climbing would mean.
17
18use crate::cdcl::Lit;
19use crate::proof::Perm;
20
21/// The action groupoid `X ⫽ G`: assignments over `nv` variables acted on by the group generated by
22/// `gens` (literal permutations). Small `nv` only — it enumerates all `2^nv` objects, which is the
23/// point: it makes the orbit collapse *visible and checkable*.
24pub struct ActionGroupoid {
25    nv: usize,
26    gens: Vec<Perm>,
27}
28
29impl ActionGroupoid {
30    pub fn new(nv: usize, gens: Vec<Perm>) -> Self {
31        ActionGroupoid { nv, gens }
32    }
33
34    /// Act by a (sign-respecting) symmetry on an assignment encoded as a bitmask: variable `v`'s value
35    /// is carried to variable `σ(+v).var`, flipped iff `σ(+v)` is negative.
36    fn act(&self, g: &Perm, a: u32) -> u32 {
37        let mut b = 0u32;
38        for v in 0..self.nv {
39            let val = (a >> v) & 1;
40            let img = g.apply(Lit::pos(v as u32));
41            let w = img.var() as usize;
42            let new_val = if img.is_positive() { val } else { 1 - val };
43            if new_val == 1 {
44                b |= 1 << w;
45            }
46        }
47        b
48    }
49
50    /// The orbit id of every assignment — `π₀(X ⫽ G)`, computed as the connected components of the
51    /// action via union-find. `orbits()[a]` is the canonical representative (smallest member) of `a`'s
52    /// orbit.
53    pub fn orbits(&self) -> Vec<u32> {
54        let total = 1u32 << self.nv;
55        let mut parent: Vec<u32> = (0..total).collect();
56        fn find(parent: &mut [u32], x: u32) -> u32 {
57            let mut r = x;
58            while parent[r as usize] != r {
59                r = parent[r as usize];
60            }
61            // path compression
62            let mut c = x;
63            while parent[c as usize] != r {
64                let next = parent[c as usize];
65                parent[c as usize] = r;
66                c = next;
67            }
68            r
69        }
70        for a in 0..total {
71            for g in &self.gens {
72                let b = self.act(g, a);
73                let (ra, rb) = (find(&mut parent, a), find(&mut parent, b));
74                if ra != rb {
75                    // union by smaller-root so representatives are canonical (smallest)
76                    if ra < rb {
77                        parent[rb as usize] = ra;
78                    } else {
79                        parent[ra as usize] = rb;
80                    }
81                }
82            }
83        }
84        (0..total).map(|a| find(&mut parent, a)).collect()
85    }
86
87    /// `|π₀(X ⫽ G)|` — the number of essentially-different worlds, i.e. exactly what symmetry breaking
88    /// reduces the search space to.
89    pub fn num_orbits(&self) -> usize {
90        let reps = self.orbits();
91        let mut distinct: Vec<u32> = reps.clone();
92        distinct.sort_unstable();
93        distinct.dedup();
94        distinct.len()
95    }
96
97    /// The full group `G` generated by `gens` (closed under composition, including the identity).
98    /// Bounded to `cap` elements so a pathological generating set can't blow up; the caller's small
99    /// examples are well within it.
100    pub fn group_elements(&self, cap: usize) -> Vec<Perm> {
101        let mut seen: std::collections::HashSet<Perm> = std::collections::HashSet::new();
102        let id = Perm::identity(self.nv);
103        seen.insert(id.clone());
104        let mut elems = vec![id];
105        let mut frontier = elems.clone();
106        while !frontier.is_empty() && elems.len() < cap {
107            let mut next = Vec::new();
108            for e in &frontier {
109                for g in &self.gens {
110                    let prod = g.compose(e); // g ∘ e
111                    if seen.insert(prod.clone()) {
112                        next.push(prod.clone());
113                        elems.push(prod);
114                        if elems.len() >= cap {
115                            return elems;
116                        }
117                    }
118                }
119            }
120            frontier = next;
121        }
122        elems
123    }
124
125    /// `π₁(X ⫽ G)` at the assignment `a` — its **stabilizer**: the group elements that fix `a`
126    /// (`g · a = a`). These are the loops at `a` in the action groupoid; the fundamental-group data of
127    /// the homotopy type at that component.
128    pub fn stabilizer_size(&self, a: u32, group: &[Perm]) -> usize {
129        group.iter().filter(|g| self.act(g, a) == a).count()
130    }
131
132    /// The size of `a`'s orbit (the connected component of `a`).
133    pub fn orbit_size(&self, a: u32) -> usize {
134        let reps = self.orbits();
135        reps.iter().filter(|&&r| r == reps[a as usize]).count()
136    }
137}
138
139#[cfg(test)]
140#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/groupoid/tests.rs"]
141mod tests;