Skip to main content

logicaffeine_proof/
affine_gfp.rs

1//! **The affine group `AGL(n,p)` over `GF(p)` — the mod-`p` generalization of the affine break.**
2//!
3//! [`crate::affine`] handles the `GF(2)` cube: the shears `xᵢ↦xᵢ⊕xⱼ` no permutation can see, and the
4//! linear obstruction (parity) that decides them. Over a prime `p` the same picture lifts: the cube
5//! becomes `GF(p)ⁿ`, signed permutations become the **monomial** group (one nonzero scalar per row/column —
6//! the `Bₙ` analog over `GF(p)`), and `AGL(n,p) = { x ↦ A x + b : A ∈ GL(n,p), b ∈ GF(p)ⁿ }` is strictly
7//! larger — its `GF(p)` shears are what mod-`p` counting (the `Count_p` / mod-`p` Tseitin families) is
8//! invariant under and the monomial breakers are blind to. This module is the `GF(p)` affine layer:
9//! the group itself, an exhaustive ground-truth detector of a `GF(p)`-system's affine symmetries (so
10//! `AGL(n,p) ⊋ monomial` is *measured*), and the certified `GF(p)` affine refutation via the mod-`p`
11//! Gaussian engine and the `emit_modp_drat` bridge. It reuses [`crate::modp`]'s `GF(p)` arithmetic
12//! throughout (`gl_order_p`, `is_invertible_modp`, `recover_from_cnf`, `solve`).
13
14use std::collections::HashSet;
15
16use crate::cdcl::Lit;
17use crate::modp::{self, ModpEquation};
18
19/// An affine map of `GF(p)ⁿ`: `x ↦ A x + b`. `matrix[i][j]` is `A`'s entry, `translation` is `b`; both
20/// reduced mod `p`. A bijection iff `A ∈ GL(n,p)`.
21#[derive(Clone, PartialEq, Eq, Debug)]
22pub struct AffineP {
23    pub p: u64,
24    pub n: usize,
25    pub matrix: Vec<Vec<u64>>,
26    pub translation: Vec<u64>,
27}
28
29impl AffineP {
30    /// The identity `x ↦ x`.
31    pub fn identity(n: usize, p: u64) -> Self {
32        let matrix = (0..n)
33            .map(|i| (0..n).map(|j| u64::from(i == j)).collect())
34            .collect();
35        AffineP {
36            p,
37            n,
38            matrix,
39            translation: vec![0; n],
40        }
41    }
42
43    /// Apply: output `i` is `(Σⱼ A[i][j]·x[j] + b[i]) mod p`.
44    pub fn apply(&self, x: &[u64]) -> Vec<u64> {
45        (0..self.n)
46            .map(|i| {
47                let s = (0..self.n).fold(0u64, |a, j| (a + self.matrix[i][j] * x[j]) % self.p);
48                (s + self.translation[i]) % self.p
49            })
50            .collect()
51    }
52
53    /// Composition `self ∘ other` over `GF(p)`: linear parts multiply, `b ↦ A_self·b_other + b_self`.
54    pub fn compose(&self, other: &AffineP) -> AffineP {
55        let (p, n) = (self.p, self.n);
56        let mut matrix = vec![vec![0u64; n]; n];
57        for (i, row) in matrix.iter_mut().enumerate() {
58            for (j, cell) in row.iter_mut().enumerate() {
59                *cell = (0..n).fold(0u64, |a, k| {
60                    (a + self.matrix[i][k] * other.matrix[k][j]) % p
61                });
62            }
63        }
64        let translation = (0..n)
65            .map(|i| {
66                let av = (0..n).fold(0u64, |a, k| {
67                    (a + self.matrix[i][k] * other.translation[k]) % p
68                });
69                (av + self.translation[i]) % p
70            })
71            .collect();
72        AffineP {
73            p,
74            n,
75            matrix,
76            translation,
77        }
78    }
79
80    /// Whether the linear part is invertible over `GF(p)` (so the map is a bijection of the cube).
81    pub fn is_bijection(&self) -> bool {
82        modp::is_invertible_modp(self.n, self.p, &self.matrix)
83    }
84
85    /// Whether the linear part is **monomial** — one nonzero entry per row and per column (a scaled
86    /// permutation). These are exactly the `Bₙ`-analog over `GF(p)`; everything else is a genuine shear.
87    pub fn is_monomial(&self) -> bool {
88        let n = self.n;
89        let rows = self
90            .matrix
91            .iter()
92            .all(|r| r.iter().filter(|&&x| x != 0).count() == 1);
93        let cols = (0..n).all(|j| (0..n).filter(|&i| self.matrix[i][j] != 0).count() == 1);
94        rows && cols
95    }
96}
97
98/// `|AGL(n,p)| = pⁿ · |GL(n,p)|`.
99pub fn agl_p_order(n: u32, p: u64) -> u128 {
100    (p as u128).pow(n) * modp::gl_order_p(n, p)
101}
102
103/// Every affine bijection of `GF(p)ⁿ` (each invertible matrix × each translation). Exhaustive — for
104/// ground-truth symmetry computation only — bounded so `p^{n²} ≤ 200_000`.
105pub fn all_affine_p_bijections(n: usize, p: u64) -> Vec<AffineP> {
106    assert!(
107        (p as u128).pow((n * n) as u32) <= 200_000,
108        "exhaustive AGL(n,p) enumeration is bounded (p^{{n²}} ≤ 200k)"
109    );
110    let decode = |mut code: u64, len: usize| -> Vec<u64> {
111        (0..len)
112            .map(|_| {
113                let d = code % p;
114                code /= p;
115                d
116            })
117            .collect()
118    };
119    let mut out = Vec::new();
120    let matrices = (p).pow((n * n) as u32);
121    let translations = (p).pow(n as u32);
122    for code in 0..matrices {
123        let flat = decode(code, n * n);
124        let matrix: Vec<Vec<u64>> = (0..n).map(|i| flat[i * n..(i + 1) * n].to_vec()).collect();
125        if !modp::is_invertible_modp(n, p, &matrix) {
126            continue;
127        }
128        for tcode in 0..translations {
129            out.push(AffineP {
130                p,
131                n,
132                matrix: matrix.clone(),
133                translation: decode(tcode, n),
134            });
135        }
136    }
137    out
138}
139
140/// The `GF(p)`-valued solutions of a mod-`p` linear system (`Σ coeffs·x ≡ rhs (mod p)` for each
141/// equation), brute force over `pⁿ` — small `n` only.
142pub fn models_p(n: usize, p: u64, equations: &[ModpEquation]) -> Vec<Vec<u64>> {
143    assert!(
144        (p as u128).pow(n as u32) <= 60_000,
145        "model enumeration is brute force — small n"
146    );
147    let total = p.pow(n as u32);
148    (0..total)
149        .filter_map(|code| {
150            let mut c = code;
151            let x: Vec<u64> = (0..n)
152                .map(|_| {
153                    let d = c % p;
154                    c /= p;
155                    d
156                })
157                .collect();
158            equations
159                .iter()
160                .all(|eq| {
161                    eq.coeffs
162                        .iter()
163                        .fold(0u64, |a, &(v, co)| (a + co * x[v]) % p)
164                        % p
165                        == eq.rhs % p
166                })
167                .then_some(x)
168        })
169        .collect()
170}
171
172/// The **affine symmetry group of a `GF(p)` model set**, computed exhaustively: every `φ ∈ AGL(n,p)` that
173/// maps the model set onto itself. The `AGL(n,p)` analogue of [`crate::affine::affine_symmetries`] — the
174/// instrument that *measures* `AGL(n,p) ⊋ monomial`.
175pub fn affine_p_symmetries(n: usize, p: u64, models: &[Vec<u64>]) -> Vec<AffineP> {
176    let set: HashSet<Vec<u64>> = models.iter().cloned().collect();
177    all_affine_p_bijections(n, p)
178        .into_iter()
179        .filter(|phi| set.iter().all(|m| set.contains(&phi.apply(m))))
180        .collect()
181}
182
183/// The clausal DRAT **certificate** for a `GF(p)` affine refutation, or `None` if the formula's mod-`p`
184/// core is not inconsistent (or the resolution expansion overruns its budget). Recovers the one-hot
185/// `GF(p)` system, finds the `Σ multiplierᵢ·equationᵢ` dependency whose left side cancels while the right
186/// does not ([`crate::modp::solve`]), and compiles it to RUP resolvent lemmas over the Boolean one-hot
187/// encoding through the [`crate::xor_drat`] bridge — `drat-trim`-checkable against the original CNF, the
188/// mod-`p` generalization of [`crate::affine::affine_refutation_drat`].
189pub fn affine_p_refutation_drat(
190    num_bool_vars: usize,
191    clauses: &[Vec<Lit>],
192) -> Option<Vec<Vec<Lit>>> {
193    crate::xor_drat::emit_modp_drat(num_bool_vars, clauses)
194}
195
196/// The outcome of the **`GF(p)` SAT-side break**.
197pub enum AffinePForced {
198    /// The mod-`p` core is inconsistent — UNSAT, with the mod-`p` DRAT certificate.
199    Refuted(Option<Vec<Vec<Lit>>>),
200    /// Forced Boolean one-hot units — implied by the mod-`p` structure, none already present.
201    Forced(Vec<Vec<Lit>>),
202    /// No recoverable mod-`p` structure, or nothing determined.
203    Unchanged,
204}
205
206/// `GF(p)` multiplication, subtraction, and (Fermat) inverse — `modp`'s are private, and these are small.
207fn gfp_mul(a: u64, b: u64, p: u64) -> u64 {
208    (a % p) * (b % p) % p
209}
210fn gfp_sub(a: u64, b: u64, p: u64) -> u64 {
211    (a % p + p - b % p) % p
212}
213fn gfp_inv(a: u64, p: u64) -> u64 {
214    let (mut result, mut base, mut exp) = (1u64, a % p, p - 2);
215    while exp > 0 {
216        if exp & 1 == 1 {
217            result = gfp_mul(result, base, p);
218        }
219        base = gfp_mul(base, base, p);
220        exp >>= 1;
221    }
222    result
223}
224
225/// **The `GF(p)` SAT-side break.** Recover the one-hot mod-`p` system ([`crate::modp::recover_from_cnf`])
226/// and solve its solution space ([`crate::modp::solve_space`]), whose kernel is the affine translation
227/// symmetry. Two structures fall out, the mod-`p` analogues of [`crate::affine::affine_reduce`]'s forced
228/// units and equivalence classes:
229///
230/// * **Forced** — a `GF(p)` variable the kernel never moves is pinned to a single value `v`; lift that
231///   through the one-hot encoding (the group's bit for `v` true, the rest false) to Boolean units.
232/// * **Linked** — variables whose kernel columns are *scalar-proportional* satisfy `x_g = c·x_rep + d` in
233///   every solution. That lifts to **value-permuted bit-equivalences** `b(g,v) ↔ b(rep, (v−d)·c⁻¹)` — the
234///   genuinely `GF(p)` shear-links no monomial break can see, the value permutation a clause equivalence
235///   cannot express on its own.
236///
237/// Every emitted clause is `GF(p)`-entailed by the formula (sound to conjoin) and new. An inconsistent
238/// core instead [`AffinePForced::Refuted`]s (certified).
239pub fn affine_p_forced(num_bool_vars: usize, clauses: &[Vec<Lit>]) -> AffinePForced {
240    let Some(rec) = modp::recover_from_cnf(num_bool_vars, clauses) else {
241        return AffinePForced::Unchanged;
242    };
243    if !modp::is_prime(rec.modulus) {
244        return AffinePForced::Unchanged; // a composite modulus is the affine_m_forced path — solve_space needs a field
245    }
246    let Some(ss) = modp::solve_space(&rec.equations, rec.num_vars, rec.modulus) else {
247        return AffinePForced::Refuted(crate::xor_drat::emit_modp_drat(num_bool_vars, clauses));
248    };
249    let p = rec.modulus;
250    let key = |c: &[Lit]| -> Vec<(u32, bool)> {
251        let mut k: Vec<(u32, bool)> = c.iter().map(|l| (l.var(), l.is_positive())).collect();
252        k.sort_unstable();
253        k
254    };
255    let existing: HashSet<Vec<(u32, bool)>> = clauses.iter().map(|c| key(c)).collect();
256    let mut out: Vec<Vec<Lit>> = Vec::new();
257    let mut push_new = |c: Vec<Lit>| {
258        if !existing.contains(&key(&c)) {
259            out.push(c);
260        }
261    };
262    // The kernel "column" of a variable — which kernel directions move it.
263    let col = |g: usize| -> Vec<u64> { ss.kernel_basis.iter().map(|kv| kv[g]).collect() };
264
265    // Forced variables (zero column) → one-hot units; everything else is grouped by its column up to a
266    // GF(p) scalar (projective equivalence) — that is exactly the linked relation.
267    let mut classes: std::collections::HashMap<Vec<u64>, Vec<usize>> =
268        std::collections::HashMap::new();
269    for g in 0..rec.num_vars {
270        let c = col(g);
271        if c.iter().all(|&x| x == 0) {
272            let val = ss.particular[g];
273            for (v, &bvar) in rec.groups[g].iter().enumerate() {
274                push_new(vec![if v as u64 == val {
275                    Lit::pos(bvar)
276                } else {
277                    Lit::neg(bvar)
278                }]);
279            }
280        } else {
281            let scale = gfp_inv(*c.iter().find(|&&x| x != 0).unwrap(), p); // normalize: first nonzero ↦ 1
282            classes
283                .entry(c.iter().map(|&x| gfp_mul(x, scale, p)).collect())
284                .or_default()
285                .push(g);
286        }
287    }
288    let mut class_list: Vec<Vec<usize>> = classes
289        .into_values()
290        .map(|mut v| {
291            v.sort_unstable();
292            v
293        })
294        .collect();
295    class_list.sort_unstable_by_key(|c| c[0]);
296    for members in &class_list {
297        if members.len() < 2 {
298            continue; // a lone variable carries no link
299        }
300        let rep = members[0];
301        let s_rep = *col(rep).iter().find(|&&x| x != 0).unwrap();
302        for &g in &members[1..] {
303            let s_g = *col(g).iter().find(|&&x| x != 0).unwrap();
304            let c_g = gfp_mul(s_g, gfp_inv(s_rep, p), p); // x_g = c_g·x_rep + d_g
305            let d_g = gfp_sub(ss.particular[g], gfp_mul(c_g, ss.particular[rep], p), p);
306            let inv_c = gfp_inv(c_g, p);
307            for v in 0..p {
308                let sv = gfp_mul(gfp_sub(v, d_g, p), inv_c, p); // b(g,v) ↔ b(rep, (v−d)·c⁻¹)
309                let (bg, br) = (rec.groups[g][v as usize], rec.groups[rep][sv as usize]);
310                push_new(vec![Lit::neg(bg), Lit::pos(br)]);
311                push_new(vec![Lit::pos(bg), Lit::neg(br)]);
312            }
313        }
314    }
315
316    if out.is_empty() {
317        AffinePForced::Unchanged
318    } else {
319        AffinePForced::Forced(out)
320    }
321}
322
323/// `|AGL(n, ℤ/m)|` for **squarefree** `m`: by CRT (`ℤ/m ≅ ∏ GF(pᵢ)`) the affine group factors as
324/// `∏ AGL(n, pᵢ)`, so the order is the product of the prime orders. `None` if `m` is not squarefree.
325pub fn agl_m_order(n: u32, m: u64) -> Option<u128> {
326    Some(
327        crate::modm::squarefree_primes(m)?
328            .iter()
329            .map(|&p| agl_p_order(n, p))
330            .product(),
331    )
332}
333
334/// Combine residues with pairwise-coprime moduli into `(value, ∏ moduli)` by incremental CRT.
335fn crt_combine(residues: &[(u64, u64)]) -> (u64, u64) {
336    let (mut acc_r, mut acc_m): (i128, i128) = (0, 1);
337    for &(r, modu) in residues {
338        let modu = modu as i128;
339        let diff = (r as i128 - acc_r).rem_euclid(modu);
340        let t = (diff * mod_inverse(acc_m.rem_euclid(modu) as u64, modu as u64) as i128)
341            .rem_euclid(modu);
342        acc_r += acc_m * t;
343        acc_m *= modu;
344        acc_r = acc_r.rem_euclid(acc_m);
345    }
346    (acc_r as u64, acc_m as u64)
347}
348
349/// The inverse of `a` mod `m` (extended Euclid) — `a` must be coprime to `m`.
350fn mod_inverse(a: u64, m: u64) -> u64 {
351    let (mut old_r, mut r): (i128, i128) = (a as i128, m as i128);
352    let (mut old_s, mut s): (i128, i128) = (1, 0);
353    while r != 0 {
354        let q = old_r / r;
355        (old_r, r) = (r, old_r - q * r);
356        (old_s, s) = (s, old_s - q * s);
357    }
358    old_s.rem_euclid(m as i128) as u64
359}
360
361/// **The composite `ℤ/m` SAT-side break** (squarefree `m`), the full mod-`m` analogue of
362/// [`affine_p_forced`] via CRT (`ℤ/m ≅ ∏ GF(pᵢ)`). Solve the system over each prime field, then for each
363/// variable combine the per-prime structure:
364///
365/// * **Forced / partially forced** — where the kernel pins `x_g` mod a set `S` of primes, `x_g` is
366///   congruent to one residue mod `∏S`; forbid every one-hot value off that residue (a single allowed
367///   value when `S` is *all* primes — the fully-forced units).
368/// * **Linked** — variables free mod *every* prime whose kernel columns are scalar-proportional mod each
369///   prime are linked over `ℤ/m` by `x_g = c·x_rep + d` with `c = CRT(cᵢ)`, `d = CRT(dᵢ)`; lift to
370///   value-permuted bit-equivalences `b(g,v) ↔ b(rep, (v−d)·c⁻¹ mod m)`.
371///
372/// Every emitted clause is `ℤ/m`-entailed and new; an inconsistent prime field [`AffinePForced::Refuted`]s.
373/// A prime modulus defers to [`affine_p_forced`]; a non-squarefree `m` (prime-power Smith case) is untouched.
374pub fn affine_m_forced(num_bool_vars: usize, clauses: &[Vec<Lit>]) -> AffinePForced {
375    let Some(rec) = modp::recover_from_cnf(num_bool_vars, clauses) else {
376        return AffinePForced::Unchanged;
377    };
378    let m = rec.modulus;
379    if modp::is_prime(m) {
380        return AffinePForced::Unchanged; // the prime path is affine_p_forced's
381    }
382    let Some(primes) = crate::modm::squarefree_primes(m) else {
383        return prime_power_forced(num_bool_vars, &rec, clauses); // non-squarefree (prime-power) branch
384    };
385    let mut spaces: Vec<crate::modp::SolutionSpaceP> = Vec::with_capacity(primes.len());
386    for &p in &primes {
387        let Some(ss) = modp::solve_space(&rec.equations, rec.num_vars, p) else {
388            return AffinePForced::Refuted(crate::xor_drat::emit_modp_drat(num_bool_vars, clauses));
389        };
390        spaces.push(ss);
391    }
392
393    let key = |c: &[Lit]| -> Vec<(u32, bool)> {
394        let mut k: Vec<(u32, bool)> = c.iter().map(|l| (l.var(), l.is_positive())).collect();
395        k.sort_unstable();
396        k
397    };
398    let existing: HashSet<Vec<(u32, bool)>> = clauses.iter().map(|c| key(c)).collect();
399    let mut out: Vec<Vec<Lit>> = Vec::new();
400    let push_new = |c: Vec<Lit>, out: &mut Vec<Vec<Lit>>| {
401        if !existing.contains(&key(&c)) {
402            out.push(c);
403        }
404    };
405    let col = |i: usize, g: usize| -> Vec<u64> {
406        spaces[i].kernel_basis.iter().map(|kk| kk[g]).collect()
407    };
408    let forced_res = |i: usize, g: usize| -> Option<u64> {
409        col(i, g)
410            .iter()
411            .all(|&x| x == 0)
412            .then(|| spaces[i].particular[g])
413    };
414
415    // PART 1 — forced / partially forced: `x_g ≡ res (mod q)` over the primes that pin it.
416    for g in 0..rec.num_vars {
417        let constraints: Vec<(u64, u64)> = primes
418            .iter()
419            .enumerate()
420            .filter_map(|(i, &p)| forced_res(i, g).map(|v| (v, p)))
421            .collect();
422        if constraints.is_empty() {
423            continue;
424        }
425        let (res, q) = crt_combine(&constraints);
426        let fully = constraints.len() == primes.len();
427        for (v, &bvar) in rec.groups[g].iter().enumerate() {
428            if (v as u64) % q != res {
429                push_new(vec![Lit::neg(bvar)], &mut out); // x_g ≠ v (off the forced residue)
430            } else if fully {
431                push_new(vec![Lit::pos(bvar)], &mut out); // the single allowed value
432            }
433        }
434    }
435
436    // PART 2 — composite links: variables free mod EVERY prime, grouped by per-prime projective signature.
437    let mut classes: std::collections::HashMap<Vec<Vec<u64>>, Vec<usize>> =
438        std::collections::HashMap::new();
439    for g in 0..rec.num_vars {
440        if (0..primes.len()).any(|i| forced_res(i, g).is_some()) {
441            continue;
442        }
443        let sig: Vec<Vec<u64>> = (0..primes.len())
444            .map(|i| {
445                let (p, c) = (primes[i], col(i, g));
446                let s = gfp_inv(*c.iter().find(|&&x| x != 0).unwrap(), p);
447                c.iter().map(|&x| gfp_mul(x, s, p)).collect()
448            })
449            .collect();
450        classes.entry(sig).or_default().push(g);
451    }
452    let mut class_list: Vec<Vec<usize>> = classes
453        .into_values()
454        .map(|mut v| {
455            v.sort_unstable();
456            v
457        })
458        .collect();
459    class_list.sort_unstable_by_key(|c| c[0]);
460    for members in &class_list {
461        if members.len() < 2 {
462            continue;
463        }
464        let rep = members[0];
465        for &g in &members[1..] {
466            let (mut cs, mut ds): (Vec<(u64, u64)>, Vec<(u64, u64)>) = (Vec::new(), Vec::new());
467            for (i, &p) in primes.iter().enumerate() {
468                let s_rep = *col(i, rep).iter().find(|&&x| x != 0).unwrap();
469                let s_g = *col(i, g).iter().find(|&&x| x != 0).unwrap();
470                let c_i = gfp_mul(s_g, gfp_inv(s_rep, p), p);
471                let d_i = gfp_sub(
472                    spaces[i].particular[g],
473                    gfp_mul(c_i, spaces[i].particular[rep], p),
474                    p,
475                );
476                cs.push((c_i, p));
477                ds.push((d_i, p));
478            }
479            let (c, _) = crt_combine(&cs);
480            let (d, _) = crt_combine(&ds);
481            let inv_c = mod_inverse(c, m);
482            for v in 0..m {
483                let sv = ((v + m - d) % m) * inv_c % m; // (v − d)·c⁻¹ mod m
484                let (bg, br) = (rec.groups[g][v as usize], rec.groups[rep][sv as usize]);
485                push_new(vec![Lit::neg(bg), Lit::pos(br)], &mut out);
486                push_new(vec![Lit::pos(bg), Lit::neg(br)], &mut out);
487            }
488        }
489    }
490
491    if out.is_empty() {
492        AffinePForced::Unchanged
493    } else {
494        AffinePForced::Forced(out)
495    }
496}
497
498/// Greatest common divisor over `u64`.
499fn gcd_u64(mut a: u64, mut b: u64) -> u64 {
500    while b != 0 {
501        (a, b) = (b, a % b);
502    }
503    a
504}
505
506/// `a·b mod q` (helper for the ring-link arithmetic).
507fn cg_mul(a: u64, b: u64, q: u64) -> u64 {
508    a % q * (b % q) % q
509}
510
511/// The kernel "column" of variable `g` in a component's solution space.
512fn kcol(ss: &crate::modm::SolutionSpaceM, g: usize) -> Vec<u64> {
513    ss.kernel_basis.iter().map(|kk| kk[g]).collect()
514}
515
516/// The composite break structure shared by the inject ([`prime_power_forced`]) and eliminate
517/// ([`affine_m_canonicalize`]) paths over a non-prime modulus: per prime-power component its Smith solution
518/// space, and per variable its tightest congruence `(res, modu)` plus (when free everywhere) its ring link
519/// `(rep, c, d)`.
520struct BreakStructure {
521    residue: Vec<(u64, u64)>,
522    link: Vec<Option<(usize, u64, u64)>>,
523}
524
525enum BreakOutcome {
526    Inconsistent,
527    Structure(BreakStructure),
528}
529
530/// Compute the [`BreakStructure`] by Smith normal form per prime-power component + CRT. `None` on overflow.
531fn composite_break_structure(
532    eqs: &[ModpEquation],
533    num_vars: usize,
534    m: u64,
535) -> Option<BreakOutcome> {
536    use crate::modm::PrimePowerSpace;
537    let factors = crate::modm::prime_power_factorize(m)?;
538    let mut spaces: Vec<(u64, u64, crate::modm::SolutionSpaceM)> =
539        Vec::with_capacity(factors.len());
540    for (p, k) in factors {
541        match crate::modm::solve_space_prime_power(eqs, num_vars, p, k) {
542            None => return None,
543            Some(PrimePowerSpace::Inconsistent) => return Some(BreakOutcome::Inconsistent),
544            Some(PrimePowerSpace::Space(ss)) => spaces.push((p, p.pow(k), ss)),
545        }
546    }
547
548    // Each variable's tightest congruence: the CRT of its per-component coset (modulus gcd(pᵏ, kernel)).
549    let residue: Vec<(u64, u64)> = (0..num_vars)
550        .map(|g| {
551            let pairs: Vec<(u64, u64)> = spaces
552                .iter()
553                .filter_map(|(_, q, ss)| {
554                    let d = kcol(ss, g).iter().fold(*q, |acc, &x| gcd_u64(acc, x));
555                    (d > 1).then(|| (ss.particular[g] % d, d))
556                })
557                .collect();
558            if pairs.is_empty() {
559                (0, 1)
560            } else {
561                (
562                    crt_combine(&pairs).0,
563                    pairs.iter().map(|&(_, d)| d).product(),
564                )
565            }
566        })
567        .collect();
568
569    // Ring links: free-everywhere variables grouped by per-component canonical column (first-unit-normalized).
570    let mut classes: std::collections::HashMap<Vec<Vec<u64>>, Vec<usize>> =
571        std::collections::HashMap::new();
572    'g: for g in 0..num_vars {
573        let mut sig: Vec<Vec<u64>> = Vec::with_capacity(spaces.len());
574        for (p, q, ss) in &spaces {
575            let c = kcol(ss, g);
576            let Some(piv) = c.iter().position(|&x| x % p != 0) else {
577                continue 'g;
578            };
579            let inv = mod_inverse(c[piv], *q);
580            sig.push(c.iter().map(|&x| x * inv % q).collect());
581        }
582        classes.entry(sig).or_default().push(g);
583    }
584    let mut link = vec![None; num_vars];
585    let mut class_list: Vec<Vec<usize>> = classes
586        .into_values()
587        .map(|mut v| {
588            v.sort_unstable();
589            v
590        })
591        .collect();
592    class_list.sort_unstable_by_key(|c| c[0]);
593    for members in &class_list {
594        if members.len() < 2 {
595            continue;
596        }
597        let rep = members[0];
598        for &g in &members[1..] {
599            let (mut cs, mut ds): (Vec<(u64, u64)>, Vec<(u64, u64)>) = (Vec::new(), Vec::new());
600            for (p, q, ss) in &spaces {
601                let (cg, cr) = (kcol(ss, g), kcol(ss, rep));
602                let piv = cr.iter().position(|&x| x % p != 0).unwrap();
603                let c_c = cg[piv] * mod_inverse(cr[piv], *q) % q;
604                let d_c = (ss.particular[g] + q - cg_mul(c_c, ss.particular[rep], *q)) % q;
605                cs.push((c_c, *q));
606                ds.push((d_c, *q));
607            }
608            link[g] = Some((rep, crt_combine(&cs).0, crt_combine(&ds).0));
609        }
610    }
611
612    Some(BreakOutcome::Structure(BreakStructure { residue, link }))
613}
614
615/// The **prime-power / mixed** (non-squarefree) branch of [`affine_m_forced`] — the full INJECT break over a
616/// ring. Computes the [`composite_break_structure`] and emits its consequences: forbid every off-residue
617/// one-hot value (forced ⇒ a single value, partial ⇒ a value-subset), and the ring links as value-permuted
618/// bit-equivalences `b(g,v) ↔ b(rep, (v−d)·c⁻¹)`. An inconsistent component refutes.
619fn prime_power_forced(
620    num_bool_vars: usize,
621    rec: &modp::ModpRecovery,
622    clauses: &[Vec<Lit>],
623) -> AffinePForced {
624    let m = rec.modulus;
625    let st = match composite_break_structure(&rec.equations, rec.num_vars, m) {
626        None => return AffinePForced::Unchanged,
627        Some(BreakOutcome::Inconsistent) => {
628            return AffinePForced::Refuted(crate::xor_drat::emit_modp_drat(num_bool_vars, clauses));
629        }
630        Some(BreakOutcome::Structure(s)) => s,
631    };
632    let key = |c: &[Lit]| -> Vec<(u32, bool)> {
633        let mut k: Vec<(u32, bool)> = c.iter().map(|l| (l.var(), l.is_positive())).collect();
634        k.sort_unstable();
635        k
636    };
637    let existing: HashSet<Vec<(u32, bool)>> = clauses.iter().map(|c| key(c)).collect();
638    let mut out: Vec<Vec<Lit>> = Vec::new();
639    let push_new = |c: Vec<Lit>, out: &mut Vec<Vec<Lit>>| {
640        if !existing.contains(&key(&c)) {
641            out.push(c);
642        }
643    };
644    for (g, &(res, modu)) in st.residue.iter().enumerate() {
645        if modu <= 1 {
646            continue;
647        }
648        for (v, &bvar) in rec.groups[g].iter().enumerate() {
649            if (v as u64) % modu != res {
650                push_new(vec![Lit::neg(bvar)], &mut out);
651            } else if modu == m {
652                push_new(vec![Lit::pos(bvar)], &mut out);
653            }
654        }
655    }
656    for g in 0..rec.num_vars {
657        if let Some((rep, c, d)) = st.link[g] {
658            let inv_c = mod_inverse(c, m);
659            for v in 0..m {
660                let sv = (v + m - d) % m * inv_c % m;
661                let (bg, br) = (rec.groups[g][v as usize], rec.groups[rep][sv as usize]);
662                push_new(vec![Lit::neg(bg), Lit::pos(br)], &mut out);
663                push_new(vec![Lit::pos(bg), Lit::neg(br)], &mut out);
664            }
665        }
666    }
667    if out.is_empty() {
668        AffinePForced::Unchanged
669    } else {
670        AffinePForced::Forced(out)
671    }
672}
673
674/// How an eliminated one-hot bit is recovered from the reduced model.
675#[derive(Clone, Debug)]
676enum BoolSub {
677    /// Pinned to a constant (a forced group's bit).
678    Const(bool),
679    /// Survives as reduced variable `new_index` (a free/representative group's bit).
680    Survive(u32),
681    /// Equal to reduced variable `new_index` — a linked group's bit aliased to its representative's,
682    /// value-permuted (`b(g,v) = b(rep, σ(v))`).
683    Alias(u32),
684}
685
686/// The reduced one-hot formula over the surviving groups, plus the lift map.
687#[derive(Clone, Debug)]
688pub struct AffinePCanonical {
689    pub num_vars: usize,
690    pub clauses: Vec<Vec<Lit>>,
691    sub: Vec<BoolSub>,
692}
693
694impl AffinePCanonical {
695    /// Lift a model of the reduced formula back over the original one-hot bits.
696    pub fn lift(&self, reduced_model: &[bool]) -> Vec<bool> {
697        self.sub
698            .iter()
699            .map(|s| match *s {
700                BoolSub::Const(c) => c,
701                BoolSub::Survive(ni) | BoolSub::Alias(ni) => reduced_model[ni as usize],
702            })
703            .collect()
704    }
705}
706
707/// The outcome of the `GF(p)` canonical elimination.
708pub enum AffinePCanon {
709    Refuted(Option<Vec<Vec<Lit>>>),
710    Canonical(AffinePCanonical),
711    Unchanged,
712}
713
714/// **The `GF(p)` canonical RREF break (elimination).** The one-hot analogue of
715/// [`crate::affine::affine_canonicalize`]: recover the mod-`p` system and solve its space, then physically
716/// *eliminate* the determined one-hot groups rather than merely injecting their consequences. A **forced**
717/// group's bits become constants; a **linked** group's bits alias to its representative's, value-permuted
718/// (`b(g,v) = b(rep, σ(v))` with `σ(v) = (v−d)·c⁻¹`). The result is an equisatisfiable formula over the
719/// surviving (free/representative) groups, with [`AffinePCanonical::lift`] to recover the eliminated bits.
720/// An inconsistent core [`AffinePCanon::Refuted`]s; a composite modulus is left to [`affine_m_forced`].
721pub fn affine_p_canonicalize(num_bool_vars: usize, clauses: &[Vec<Lit>]) -> AffinePCanon {
722    let Some(rec) = modp::recover_from_cnf(num_bool_vars, clauses) else {
723        return AffinePCanon::Unchanged;
724    };
725    let p = rec.modulus;
726    if !modp::is_prime(p) {
727        return AffinePCanon::Unchanged;
728    }
729    let Some(ss) = modp::solve_space(&rec.equations, rec.num_vars, p) else {
730        return AffinePCanon::Refuted(crate::xor_drat::emit_modp_drat(num_bool_vars, clauses));
731    };
732
733    // Classify each GF(p) variable: forced to a constant, or a member of a projective (linked) class.
734    enum Role {
735        Forced(u64),
736        Survive,
737        Linked { rep: usize, c: u64, d: u64 },
738    }
739    let col = |g: usize| -> Vec<u64> { ss.kernel_basis.iter().map(|k| k[g]).collect() };
740    let mut role: Vec<Role> = Vec::with_capacity(rec.num_vars);
741    let mut classes: std::collections::HashMap<Vec<u64>, Vec<usize>> =
742        std::collections::HashMap::new();
743    for g in 0..rec.num_vars {
744        let c = col(g);
745        if c.iter().all(|&x| x == 0) {
746            role.push(Role::Forced(ss.particular[g]));
747        } else {
748            let s = gfp_inv(*c.iter().find(|&&x| x != 0).unwrap(), p);
749            classes
750                .entry(c.iter().map(|&x| gfp_mul(x, s, p)).collect())
751                .or_default()
752                .push(g);
753            role.push(Role::Survive); // provisional; linked members are rewritten below
754        }
755    }
756    for members in classes.values() {
757        let mut ms = members.clone();
758        ms.sort_unstable();
759        let rep = ms[0];
760        let s_rep = *col(rep).iter().find(|&&x| x != 0).unwrap();
761        for &g in &ms[1..] {
762            let s_g = *col(g).iter().find(|&&x| x != 0).unwrap();
763            let c = gfp_mul(s_g, gfp_inv(s_rep, p), p);
764            let d = gfp_sub(ss.particular[g], gfp_mul(c, ss.particular[rep], p), p);
765            role[g] = Role::Linked { rep, c, d };
766        }
767    }
768
769    // Assign reduced indices to the surviving bits (free/representative groups, then any non-group bits).
770    let mut in_group = vec![false; num_bool_vars];
771    for grp in &rec.groups {
772        for &b in grp {
773            in_group[b as usize] = true;
774        }
775    }
776    let mut new_idx: Vec<Option<u32>> = vec![None; num_bool_vars];
777    let mut next = 0u32;
778    for g in 0..rec.num_vars {
779        if matches!(role[g], Role::Survive) {
780            for &b in &rec.groups[g] {
781                new_idx[b as usize] = Some(next);
782                next += 1;
783            }
784        }
785    }
786    for (b, slot) in new_idx.iter_mut().enumerate() {
787        if !in_group[b] {
788            *slot = Some(next);
789            next += 1;
790        }
791    }
792    let reduced_nv = next as usize;
793
794    // Build the per-bit substitution.
795    let mut sub = vec![BoolSub::Const(false); num_bool_vars];
796    for (b, slot) in new_idx.iter().enumerate() {
797        if let Some(ni) = slot {
798            sub[b] = BoolSub::Survive(*ni); // surviving + non-group bits
799        }
800    }
801    for g in 0..rec.num_vars {
802        match role[g] {
803            Role::Forced(val) => {
804                for (v, &b) in rec.groups[g].iter().enumerate() {
805                    sub[b as usize] = BoolSub::Const(v as u64 == val);
806                }
807            }
808            Role::Survive => {} // already Survive
809            Role::Linked { rep, c, d } => {
810                let inv_c = gfp_inv(c, p);
811                for (v, &b) in rec.groups[g].iter().enumerate() {
812                    let sv = gfp_mul(gfp_sub(v as u64, d, p), inv_c, p); // σ(v) = (v − d)·c⁻¹
813                    let rep_b = rec.groups[rep][sv as usize];
814                    sub[b as usize] = BoolSub::Alias(new_idx[rep_b as usize].unwrap());
815                }
816            }
817        }
818    }
819    if !sub
820        .iter()
821        .any(|s| matches!(s, BoolSub::Const(_) | BoolSub::Alias(_)))
822    {
823        return AffinePCanon::Unchanged; // nothing eliminated
824    }
825
826    // Apply the substitution to every clause, staying in CNF.
827    let mut out: Vec<Vec<Lit>> = Vec::new();
828    'clause: for c in clauses {
829        let mut seen: std::collections::HashMap<u32, bool> = std::collections::HashMap::new();
830        let mut lits: Vec<Lit> = Vec::new();
831        for l in c {
832            let (ni, pol) = match sub[l.var() as usize] {
833                BoolSub::Const(cst) => {
834                    if cst == l.is_positive() {
835                        continue 'clause; // literal true ⇒ clause satisfied
836                    }
837                    continue; // literal false ⇒ drop it
838                }
839                BoolSub::Survive(ni) | BoolSub::Alias(ni) => (ni, l.is_positive()),
840            };
841            match seen.get(&ni) {
842                Some(&prev) if prev != pol => continue 'clause, // tautology
843                Some(_) => continue,                            // duplicate
844                None => {
845                    seen.insert(ni, pol);
846                    lits.push(Lit::new(ni, pol));
847                }
848            }
849        }
850        out.push(lits);
851    }
852    AffinePCanon::Canonical(AffinePCanonical {
853        num_vars: reduced_nv,
854        clauses: out,
855        sub,
856    })
857}
858
859/// **The composite-ring canonical elimination.** The `ℤ/m` analogue of [`affine_p_canonicalize`] and the
860/// eliminate twin of `prime_power_forced`: over a non-prime modulus, recover the mod-`m` system, take its
861/// `composite_break_structure`, and physically *eliminate* the determined one-hot structure rather than
862/// merely injecting it. A **forced** group (`x_g` pinned to a single value) becomes constants; a **partially
863/// forced** group (`x_g` confined to a coset `v ≡ res (mod modu)`, `1 < modu < m`) keeps only its on-coset
864/// bits, the rest pinned false; a **linked** group's bits alias its representative's, value-permuted
865/// (`b(g,v) = b(rep, σ(v))`, `σ(v) = (v−d)·c⁻¹ mod m`). The result is equisatisfiable over the surviving
866/// bits, with [`AffinePCanonical::lift`] to recover the rest. An inconsistent component
867/// [`AffinePCanon::Refuted`]s; a prime modulus is left to [`affine_p_canonicalize`].
868pub fn affine_m_canonicalize(num_bool_vars: usize, clauses: &[Vec<Lit>]) -> AffinePCanon {
869    let Some(rec) = modp::recover_from_cnf(num_bool_vars, clauses) else {
870        return AffinePCanon::Unchanged;
871    };
872    let m = rec.modulus;
873    if modp::is_prime(m) {
874        return AffinePCanon::Unchanged; // prime ⇒ the field path
875    }
876    let st = match composite_break_structure(&rec.equations, rec.num_vars, m) {
877        None => return AffinePCanon::Unchanged,
878        Some(BreakOutcome::Inconsistent) => {
879            return AffinePCanon::Refuted(crate::xor_drat::emit_modp_drat(num_bool_vars, clauses));
880        }
881        Some(BreakOutcome::Structure(s)) => s,
882    };
883
884    enum Role {
885        Forced(u64),
886        Partial { res: u64, modu: u64 },
887        Survive,
888        Linked { rep: usize, c: u64, d: u64 },
889    }
890    let role: Vec<Role> = (0..rec.num_vars)
891        .map(|g| {
892            let (res, modu) = st.residue[g];
893            if modu == m {
894                Role::Forced(res)
895            } else if modu > 1 {
896                Role::Partial { res, modu }
897            } else if let Some((rep, c, d)) = st.link[g] {
898                Role::Linked { rep, c, d }
899            } else {
900                Role::Survive
901            }
902        })
903        .collect();
904
905    // Assign reduced indices to the surviving bits: free groups' bits, partial groups' on-coset bits, then
906    // any non-group bits.
907    let mut in_group = vec![false; num_bool_vars];
908    for grp in &rec.groups {
909        for &b in grp {
910            in_group[b as usize] = true;
911        }
912    }
913    let mut new_idx: Vec<Option<u32>> = vec![None; num_bool_vars];
914    let mut next = 0u32;
915    for g in 0..rec.num_vars {
916        match role[g] {
917            Role::Survive => {
918                for &b in &rec.groups[g] {
919                    new_idx[b as usize] = Some(next);
920                    next += 1;
921                }
922            }
923            Role::Partial { res, modu } => {
924                for (v, &b) in rec.groups[g].iter().enumerate() {
925                    if (v as u64) % modu == res {
926                        new_idx[b as usize] = Some(next);
927                        next += 1;
928                    }
929                }
930            }
931            _ => {}
932        }
933    }
934    for (b, slot) in new_idx.iter_mut().enumerate() {
935        if !in_group[b] {
936            *slot = Some(next);
937            next += 1;
938        }
939    }
940    let reduced_nv = next as usize;
941
942    // Build the per-bit substitution. Surviving (free, on-coset, non-group) bits are set above; forced bits
943    // become constants, off-coset partial bits false, linked bits value-permuted aliases.
944    let mut sub = vec![BoolSub::Const(false); num_bool_vars];
945    for (b, slot) in new_idx.iter().enumerate() {
946        if let Some(ni) = slot {
947            sub[b] = BoolSub::Survive(*ni);
948        }
949    }
950    for g in 0..rec.num_vars {
951        match role[g] {
952            Role::Forced(val) => {
953                for (v, &b) in rec.groups[g].iter().enumerate() {
954                    sub[b as usize] = BoolSub::Const(v as u64 == val);
955                }
956            }
957            Role::Partial { .. } | Role::Survive => {} // already set by the surviving-bit pass
958            Role::Linked { rep, c, d } => {
959                let inv_c = mod_inverse(c, m);
960                for (v, &b) in rec.groups[g].iter().enumerate() {
961                    let sv = (v as u64 + m - d) % m * inv_c % m; // σ(v) = (v − d)·c⁻¹
962                    let rep_b = rec.groups[rep][sv as usize];
963                    sub[b as usize] = BoolSub::Alias(new_idx[rep_b as usize].unwrap());
964                }
965            }
966        }
967    }
968    if !sub
969        .iter()
970        .any(|s| matches!(s, BoolSub::Const(_) | BoolSub::Alias(_)))
971    {
972        return AffinePCanon::Unchanged; // nothing eliminated
973    }
974
975    // Apply the substitution to every clause, staying in CNF.
976    let mut out: Vec<Vec<Lit>> = Vec::new();
977    'clause: for c in clauses {
978        let mut seen: std::collections::HashMap<u32, bool> = std::collections::HashMap::new();
979        let mut lits: Vec<Lit> = Vec::new();
980        for l in c {
981            let (ni, pol) = match sub[l.var() as usize] {
982                BoolSub::Const(cst) => {
983                    if cst == l.is_positive() {
984                        continue 'clause; // literal true ⇒ clause satisfied
985                    }
986                    continue; // literal false ⇒ drop it
987                }
988                BoolSub::Survive(ni) | BoolSub::Alias(ni) => (ni, l.is_positive()),
989            };
990            match seen.get(&ni) {
991                Some(&prev) if prev != pol => continue 'clause, // tautology
992                Some(_) => continue,                            // duplicate
993                None => {
994                    seen.insert(ni, pol);
995                    lits.push(Lit::new(ni, pol));
996                }
997            }
998        }
999        out.push(lits);
1000    }
1001    AffinePCanon::Canonical(AffinePCanonical {
1002        num_vars: reduced_nv,
1003        clauses: out,
1004        sub,
1005    })
1006}
1007
1008#[cfg(test)]
1009#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/affine_gfp/tests.rs"]
1010mod tests;