logicaffeine_proof/affine.rs
1//! **The affine group `AGL(n,2)` — the symmetry a permutation break cannot see.**
2//!
3//! The clause-level symmetry breakers (`symmetry_detect`, `sym_certify`) quotient by the hyperoctahedral
4//! group `Bₙ` of signed variable permutations. `Bₙ` is exactly the subgroup of `AGL(n,2)` (affine
5//! bijections `x ↦ A x ⊕ b` of the cube `GF(2)ⁿ`) whose linear part `A` is a permutation matrix. The
6//! census proved the clause breakers are *complete* for `Bₙ` — yet `AGL(n,2) ⊋ Bₙ`, and the gap is the
7//! **shears** `xᵢ ↦ xᵢ ⊕ xⱼ`. A shear maps an axis-aligned subcube (a clause) to a *non*-subcube, so no
8//! amount of clause permutation can reach it. That gap is precisely why parity / Tseitin formulas — affine
9//! invariant, `Bₙ`-rigid — defeat clause symmetry breaking and need a linear-algebra engine instead.
10//!
11//! This module is that engine, at the symmetry level: the `AGL(n,2)` group itself, an exhaustive
12//! ground-truth detector of a formula's affine symmetries (so `AGL ⊋ Bₙ` is *measured*, not asserted), and
13//! the affine **break** — recover the formula's `GF(2)`-linear substructure, Gauss-eliminate it, and either
14//! refute an inconsistent linear core or inject the forced units / equivalences (the linear consequences no
15//! single clause states) that collapse the residual search.
16
17use std::collections::HashSet;
18
19use crate::cdcl::Lit;
20use crate::gf2;
21
22/// An affine map of the Boolean cube `GF(2)ⁿ`: `x ↦ A x ⊕ b`. `matrix[i]` is row `i` of `A` as a
23/// coefficient bitmask over the low `n` bits; `translation` is `b`. It is a bijection iff `A ∈ GL(n,2)`.
24#[derive(Clone, PartialEq, Eq, Debug)]
25pub struct Affine {
26 pub n: usize,
27 pub matrix: Vec<u64>,
28 pub translation: u64,
29}
30
31impl Affine {
32 /// The identity `x ↦ x` (`A = I`, `b = 0`).
33 pub fn identity(n: usize) -> Self {
34 Affine {
35 n,
36 matrix: (0..n).map(|i| 1u64 << i).collect(),
37 translation: 0,
38 }
39 }
40
41 /// Apply the map to a point `x` (low `n` bits): output bit `i` is `parity(row_i · x) ⊕ b_i`.
42 pub fn apply(&self, x: u64) -> u64 {
43 let mut y = 0u64;
44 for i in 0..self.n {
45 let dot = (self.matrix[i] & x).count_ones() & 1;
46 let bit = dot ^ ((self.translation >> i) & 1) as u32;
47 y |= (bit as u64) << i;
48 }
49 y
50 }
51
52 /// Composition `self ∘ other`: `(self ∘ other)(x) = self(other(x))`. The linear parts multiply over
53 /// `GF(2)` and the translations combine as `A_self · b_other ⊕ b_self`.
54 pub fn compose(&self, other: &Affine) -> Affine {
55 debug_assert_eq!(self.n, other.n);
56 // Row i of A_self·A_other = XOR of A_other's rows selected by the set bits of A_self's row i.
57 let mut matrix = vec![0u64; self.n];
58 for i in 0..self.n {
59 let mut row = 0u64;
60 let mut sel = self.matrix[i];
61 while sel != 0 {
62 let k = sel.trailing_zeros() as usize;
63 row ^= other.matrix[k];
64 sel &= sel - 1;
65 }
66 matrix[i] = row;
67 }
68 // A_self applied to b_other, then ⊕ b_self.
69 let mut translation = self.translation;
70 for i in 0..self.n {
71 let dot = (self.matrix[i] & other.translation).count_ones() & 1;
72 translation ^= (dot as u64) << i;
73 }
74 Affine {
75 n: self.n,
76 matrix,
77 translation,
78 }
79 }
80
81 /// Whether the linear part is invertible (so the map is a bijection of the cube).
82 pub fn is_bijection(&self) -> bool {
83 gf2::is_invertible_gf2(self.n as u32, &self.matrix)
84 }
85}
86
87/// `|AGL(n,2)| = 2ⁿ · |GL(n,2)|` — the `2ⁿ` translations times the invertible linear parts.
88pub fn agl_order(n: u32) -> u128 {
89 (1u128 << n) * gf2::gl_order(n)
90}
91
92/// **The affine automorphism group order of a `k`-dimensional affine subspace of `GF(2)ⁿ`** — i.e. the number
93/// of affine maps `x ↦ Ax ⊕ b` fixing the model set of an XOR-defined family whose solution space has
94/// dimension `k`. In *closed form*, computable at every `n` without enumerating `AGL(n,2)`:
95/// `|GL(k,2)| · |GL(n−k,2)| · 2^{k(n−k)} · 2^k` — the block-upper-triangular invertible linear parts (`GL(k)`
96/// on the subspace, `GL(n−k)` on the quotient, `2^{k(n−k)}` shears between them) times the `2^k` in-subspace
97/// translations. The scalable affine-symmetry detector for the whole class of linear families: `Bₙ` sees a
98/// vanishing fraction of it (see the tests).
99pub fn affine_subspace_agl_order(n: u32, k: u32) -> u128 {
100 debug_assert!(k <= n);
101 gf2::gl_order(k) * gf2::gl_order(n - k) * (1u128 << (k * (n - k))) * (1u128 << k)
102}
103
104/// Every affine bijection of `GF(2)ⁿ` (each invertible matrix × each translation). Exhaustive — for
105/// ground-truth symmetry computation only — so it is capped at `n ≤ 4` (`|AGL(4,2)| = 322 560`).
106pub fn all_affine_bijections(n: usize) -> Vec<Affine> {
107 assert!(
108 n <= 4,
109 "exhaustive AGL enumeration is for ground-truth tests only (n ≤ 4)"
110 );
111 let mut out = Vec::new();
112 let total_matrices = 1u64 << (n * n);
113 for code in 0..total_matrices {
114 let matrix: Vec<u64> = (0..n).map(|i| (code >> (i * n)) & ((1 << n) - 1)).collect();
115 if !gf2::is_invertible_gf2(n as u32, &matrix) {
116 continue;
117 }
118 for translation in 0..(1u64 << n) {
119 out.push(Affine {
120 n,
121 matrix: matrix.clone(),
122 translation,
123 });
124 }
125 }
126 out
127}
128
129/// The satisfying assignments of a CNF, each packed into the low `num_vars` bits of a `u64`. Brute force
130/// over `2^{num_vars}` — small `n` only (the census / symmetry-measurement regime).
131pub fn models_of(num_vars: usize, clauses: &[Vec<Lit>]) -> Vec<u64> {
132 assert!(
133 num_vars <= 24,
134 "model enumeration is brute force — small n only"
135 );
136 (0u64..(1u64 << num_vars))
137 .filter(|&x| {
138 clauses.iter().all(|c| {
139 c.iter()
140 .any(|l| ((x >> l.var()) & 1 == 1) == l.is_positive())
141 })
142 })
143 .collect()
144}
145
146/// The **affine symmetry group of a formula**, computed exhaustively: every `φ ∈ AGL(n,2)` that maps the
147/// model set onto itself (`φ` a bijection, so `φ(models) = models` iff `φ` maps each model to a model).
148/// This is the `AGL(n,2)` analogue of `symmetry_detect::find_generators` (which finds only the `Bₙ`
149/// part), and it is exact for `n ≤ 4` — the instrument that *measures* `AGL ⊋ Bₙ`.
150pub fn affine_symmetries(num_vars: usize, clauses: &[Vec<Lit>]) -> Vec<Affine> {
151 let models: HashSet<u64> = models_of(num_vars, clauses).into_iter().collect();
152 all_affine_bijections(num_vars)
153 .into_iter()
154 .filter(|phi| models.iter().all(|&m| models.contains(&phi.apply(m))))
155 .collect()
156}
157
158/// Pack XOR equations into `(coefficient-mask, rhs)` rows over the low bits, for [`gf2::solve_gf2`].
159fn eqs_to_rows(eqs: &[crate::xorsat::XorEquation]) -> (Vec<u64>, Vec<bool>) {
160 let mut rows = Vec::with_capacity(eqs.len());
161 let mut rhs = Vec::with_capacity(eqs.len());
162 for eq in eqs {
163 let mut mask = 0u64;
164 for &v in &eq.vars {
165 mask |= 1u64 << v;
166 }
167 rows.push(mask);
168 rhs.push(eq.rhs);
169 }
170 (rows, rhs)
171}
172
173/// Recover the `GF(2)`-linear substructure of a CNF: the XOR equations its clauses encode (units,
174/// binary equivalences, and complete wrong-parity bundles), as `(coefficient-mask, rhs)` rows over the
175/// low `num_vars` bits. `None` when there is no linear structure or `num_vars` exceeds the `u64` mask.
176pub fn recover_linear_system(
177 num_vars: usize,
178 clauses: &[Vec<Lit>],
179) -> Option<(Vec<u64>, Vec<bool>)> {
180 if num_vars > 63 {
181 return None;
182 }
183 let eqs = crate::lyapunov::extract_xor(num_vars, clauses);
184 if eqs.is_empty() {
185 return None;
186 }
187 Some(eqs_to_rows(&eqs))
188}
189
190/// The clausal DRAT **certificate** for an affine refutation, or `None` if the formula's linear core is
191/// not inconsistent (or `num_vars` exceeds the `u64` mask, or the resolution expansion overruns its
192/// budget). Recovers the XOR system, finds the GF(2) linear dependency that sums to `0 = 1`
193/// ([`crate::xorsat::solve`]), and compiles it to RUP resolvent lemmas through the [`crate::xor_drat`]
194/// bridge — the same path `Route::Parity` uses, so it is `drat-trim`-checkable against the original CNF.
195pub fn affine_refutation_drat(num_vars: usize, clauses: &[Vec<Lit>]) -> Option<Vec<Vec<Lit>>> {
196 if num_vars > 63 {
197 return None;
198 }
199 let eqs = crate::lyapunov::extract_xor(num_vars, clauses);
200 match crate::xorsat::solve(&eqs, num_vars) {
201 crate::xorsat::XorOutcome::Unsat(refutation) => {
202 crate::xor_drat::emit_xor_drat(&eqs, &refutation)
203 }
204 crate::xorsat::XorOutcome::Sat(_) => None,
205 }
206}
207
208/// The outcome of the affine break.
209#[derive(Clone, Debug, PartialEq, Eq)]
210pub enum AffineOutcome {
211 /// The recovered linear system is inconsistent (`0 = 1`) ⇒ the formula is UNSAT, by an obstruction no
212 /// clause permutation can express. The payload is the **certificate**: the GF(2) linear-dependency
213 /// refutation compiled to clausal DRAT resolvents through the [`crate::xor_drat`] bridge (a sequence
214 /// of RUP lemmas that `drat-trim` / [`crate::rup::check_refutation`] verifies against the original
215 /// CNF), or `None` when the resolution expansion exceeds its budget — the verdict still stands on the
216 /// native algebraic certificate, exactly as the `Route::Parity` cut does.
217 Refuted(Option<Vec<Vec<Lit>>>),
218 /// Consistent, but Gauss elimination forced linear consequences — units and/or equivalences not stated
219 /// by any single clause. The carried clauses are sound to conjoin (implied by the formula) and are
220 /// genuinely new (none already present), so adding them strictly strengthens it for search.
221 Forced(Vec<Vec<Lit>>),
222 /// No linear structure, or nothing new derivable.
223 Unchanged,
224}
225
226/// Sorted `(var, polarity)` key for clause-set membership.
227fn canon(clause: &[Lit]) -> Vec<(u32, bool)> {
228 let mut k: Vec<(u32, bool)> = clause.iter().map(|l| (l.var(), l.is_positive())).collect();
229 k.sort_unstable();
230 k.dedup();
231 k
232}
233
234/// The **affine `GF(2)` break.** Recover the formula's linear substructure and Gauss-eliminate it
235/// ([`gf2::solve_gf2`]): an inconsistent core [`AffineOutcome::Refuted`]s outright; otherwise the
236/// elimination's [`gf2::SolutionSpace`] exposes which variables are *forced* (the kernel never moves them
237/// ⇒ a unit) and which are *locked together* (the kernel moves them in lockstep ⇒ an equivalence), and we
238/// return those consequences as new clauses ([`AffineOutcome::Forced`]) — the linear inferences the
239/// permutation breaker structurally cannot make.
240pub fn affine_reduce(num_vars: usize, clauses: &[Vec<Lit>]) -> AffineOutcome {
241 if num_vars > 63 {
242 return AffineOutcome::Unchanged;
243 }
244 let eqs = crate::lyapunov::extract_xor(num_vars, clauses);
245 if eqs.is_empty() {
246 return AffineOutcome::Unchanged;
247 }
248 // Inconsistent linear core ⇒ UNSAT, certified through the xor_drat bridge: the GF(2) linear-dependency
249 // witness compiles to clausal DRAT resolvents that re-check against the original CNF.
250 if let crate::xorsat::XorOutcome::Unsat(refutation) = crate::xorsat::solve(&eqs, num_vars) {
251 return AffineOutcome::Refuted(crate::xor_drat::emit_xor_drat(&eqs, &refutation));
252 }
253 // Consistent: derive forced consequences from the RREF solution space.
254 let (rows, rhs) = eqs_to_rows(&eqs);
255 let Some(ss) = gf2::solve_gf2(num_vars, &rows, &rhs) else {
256 return AffineOutcome::Unchanged; // unreachable: xorsat consistent ⇒ solve_gf2 consistent
257 };
258
259 let existing: HashSet<Vec<(u32, bool)>> = clauses.iter().map(|c| canon(c)).collect();
260 let mut forced: Vec<Vec<Lit>> = Vec::new();
261 let push_new = |clause: Vec<Lit>, forced: &mut Vec<Vec<Lit>>| {
262 if !existing.contains(&canon(&clause)) {
263 forced.push(clause);
264 }
265 };
266
267 // A variable the kernel never moves is pinned to its value in every solution — a forced unit.
268 let mut is_forced = vec![false; num_vars];
269 for v in 0..num_vars {
270 if ss.kernel_basis.iter().all(|k| !k[v]) {
271 is_forced[v] = true;
272 push_new(vec![Lit::new(v as u32, ss.particular[v])], &mut forced);
273 }
274 }
275 // A pair the kernel always moves together is locked into `x_u ⊕ x_v = c` in every solution — a forced
276 // equivalence. (Skip pairs with a forced endpoint; the units already pin them.)
277 for u in 0..num_vars {
278 if is_forced[u] {
279 continue;
280 }
281 for v in (u + 1)..num_vars {
282 if is_forced[v] {
283 continue;
284 }
285 if ss.kernel_basis.iter().all(|k| k[u] == k[v]) {
286 let (lu, lv) = (u as u32, v as u32);
287 if ss.particular[u] ^ ss.particular[v] {
288 // x_u ≠ x_v: (x_u ∨ x_v) ∧ (¬x_u ∨ ¬x_v)
289 push_new(vec![Lit::pos(lu), Lit::pos(lv)], &mut forced);
290 push_new(vec![Lit::neg(lu), Lit::neg(lv)], &mut forced);
291 } else {
292 // x_u = x_v: (¬x_u ∨ x_v) ∧ (x_u ∨ ¬x_v)
293 push_new(vec![Lit::neg(lu), Lit::pos(lv)], &mut forced);
294 push_new(vec![Lit::pos(lu), Lit::neg(lv)], &mut forced);
295 }
296 }
297 }
298 }
299
300 if forced.is_empty() {
301 AffineOutcome::Unchanged
302 } else {
303 AffineOutcome::Forced(forced)
304 }
305}
306
307/// How an eliminated variable is recovered from the reduced model — its place in the affine quotient.
308#[derive(Clone, Debug, PartialEq, Eq)]
309enum VarSub {
310 /// Forced to a constant by the linear core (the kernel never moves it).
311 Const(bool),
312 /// Survives as reduced variable `new_index` (a free generator or a class representative).
313 Survive(u32),
314 /// Equal to reduced variable `new_index`, XORed with `flip` — a member of an equivalence class.
315 Alias(u32, bool),
316}
317
318/// The result of the canonical affine reduction: an equisatisfiable formula over the **free generators**
319/// (the linearly-determined variables eliminated), plus the map to lift a reduced model back to the full
320/// space. This is the affine analogue of breaking a permutation orbit down to one representative — here
321/// the RREF canonicalizes the affine structure and the determined coordinates fall away.
322#[derive(Clone, Debug)]
323pub struct AffineCanonical {
324 pub num_vars: usize,
325 pub clauses: Vec<Vec<Lit>>,
326 sub: Vec<VarSub>,
327}
328
329impl AffineCanonical {
330 /// Lift a model of the reduced formula back to a model over the original variables, reconstructing
331 /// each eliminated coordinate from its canonical definition (constant, or alias of a survivor).
332 pub fn lift(&self, reduced_model: &[bool]) -> Vec<bool> {
333 self.sub
334 .iter()
335 .map(|s| match *s {
336 VarSub::Const(c) => c,
337 VarSub::Survive(ni) => reduced_model[ni as usize],
338 VarSub::Alias(ni, flip) => reduced_model[ni as usize] ^ flip,
339 })
340 .collect()
341 }
342}
343
344/// The outcome of the **canonical RREF break**.
345pub enum AffineCanon {
346 /// The linear core is inconsistent — UNSAT, with the xor_drat certificate (as [`AffineOutcome::Refuted`]).
347 Refuted(Option<Vec<Vec<Lit>>>),
348 /// Reduced to the free generators, with the lifting map.
349 Canonical(AffineCanonical),
350 /// No linear structure, or nothing determined to eliminate.
351 Unchanged,
352}
353
354/// **The affine SBP — the canonical RREF break.** Recover the formula's GF(2)-linear substructure and
355/// take its reduced row-echelon form (via [`gf2::solve_gf2`], whose kernel basis is the affine
356/// translation symmetry). The RREF partitions variables into *free generators* and *determined*
357/// coordinates: every variable the kernel never moves is **forced** to a constant, and every set the
358/// kernel moves in lockstep is an **equivalence class** collapsing to one representative. Substituting
359/// those determined coordinates out yields an equisatisfiable formula over the free generators alone — the
360/// affine symmetry quotiented to a canonical representative, exactly as a permutation lex-leader collapses
361/// an orbit. An inconsistent core instead [`AffineCanon::Refuted`]s (certified). Sound: the eliminated
362/// relations are GF(2)-entailed by the formula, so [`AffineCanonical::lift`] turns any reduced model into
363/// a full one.
364pub fn affine_canonicalize(num_vars: usize, clauses: &[Vec<Lit>]) -> AffineCanon {
365 if num_vars > 63 {
366 return AffineCanon::Unchanged;
367 }
368 let eqs = crate::lyapunov::extract_xor(num_vars, clauses);
369 if eqs.is_empty() {
370 return AffineCanon::Unchanged;
371 }
372 if let crate::xorsat::XorOutcome::Unsat(refutation) = crate::xorsat::solve(&eqs, num_vars) {
373 return AffineCanon::Refuted(crate::xor_drat::emit_xor_drat(&eqs, &refutation));
374 }
375 let (rows, rhs) = eqs_to_rows(&eqs);
376 let Some(ss) = gf2::solve_gf2(num_vars, &rows, &rhs) else {
377 return AffineCanon::Unchanged; // unreachable: xorsat consistent ⇒ solve_gf2 consistent
378 };
379
380 // A variable's "kernel column" — which kernel-basis vectors move it. Forced variables have an
381 // all-zero column; variables sharing a column move in lockstep (an equivalence class).
382 let kdim = ss.kernel_basis.len();
383 let column = |v: usize| -> Vec<bool> { (0..kdim).map(|i| ss.kernel_basis[i][v]).collect() };
384 let zero = vec![false; kdim];
385
386 let mut sub = vec![VarSub::Const(false); num_vars];
387 let mut groups: std::collections::HashMap<Vec<bool>, Vec<usize>> =
388 std::collections::HashMap::new();
389 for v in 0..num_vars {
390 let col = column(v);
391 if col == zero {
392 sub[v] = VarSub::Const(ss.particular[v]); // forced
393 } else {
394 groups.entry(col).or_default().push(v);
395 }
396 }
397 // Each class collapses to its lowest-index representative; assign reduced indices in representative order.
398 let mut classes: Vec<Vec<usize>> = groups
399 .into_values()
400 .map(|mut g| {
401 g.sort_unstable();
402 g
403 })
404 .collect();
405 classes.sort_unstable_by_key(|g| g[0]);
406 for (new_index, members) in classes.iter().enumerate() {
407 let rep = members[0];
408 let rep_par = ss.particular[rep];
409 for &v in members {
410 sub[v] = if v == rep {
411 VarSub::Survive(new_index as u32)
412 } else {
413 VarSub::Alias(new_index as u32, ss.particular[v] ^ rep_par) // x_v = x_rep ⊕ flip
414 };
415 }
416 }
417 let reduced_nv = classes.len();
418 if !sub
419 .iter()
420 .any(|s| matches!(s, VarSub::Const(_) | VarSub::Alias(_, _)))
421 {
422 return AffineCanon::Unchanged; // nothing determined to eliminate
423 }
424
425 // Apply the substitution to every clause (linear and clausal alike), staying in CNF.
426 let mut out: Vec<Vec<Lit>> = Vec::new();
427 'clause: for c in clauses {
428 let mut seen: std::collections::HashMap<u32, bool> = std::collections::HashMap::new();
429 let mut lits: Vec<Lit> = Vec::new();
430 for l in c {
431 let (ni, pol) = match sub[l.var() as usize] {
432 VarSub::Const(cst) => {
433 if cst == l.is_positive() {
434 continue 'clause; // literal true ⇒ clause satisfied, drop it
435 }
436 continue; // literal false ⇒ drop the literal
437 }
438 VarSub::Survive(ni) => (ni, l.is_positive()),
439 VarSub::Alias(ni, flip) => (ni, l.is_positive() ^ flip),
440 };
441 match seen.get(&ni) {
442 Some(&prev) if prev != pol => continue 'clause, // x ∨ ¬x ⇒ tautology, drop the clause
443 Some(_) => continue, // duplicate literal
444 None => {
445 seen.insert(ni, pol);
446 lits.push(Lit::new(ni, pol));
447 }
448 }
449 }
450 out.push(lits); // a now-empty clause is a sound UNSAT marker the solver will catch
451 }
452
453 AffineCanon::Canonical(AffineCanonical {
454 num_vars: reduced_nv,
455 clauses: out,
456 sub,
457 })
458}
459
460#[cfg(test)]
461#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/affine/tests.rs"]
462mod tests;