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;