Skip to main content

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;