Skip to main content

logicaffeine_proof/
polycalc.rs

1//! Polynomial Calculus / Nullstellensatz over `GF(2)` — the algebraic proof system that **subsumes the
2//! linear cuts** (parity is its degree-1 fragment) and, at higher degree, refutes strictly more.
3//!
4//! A CNF is unsatisfiable iff the constant polynomial `1` lies in the ideal generated by the clause
5//! polynomials over the *multilinear* `GF(2)` ring (where `x² = x`, so every monomial is squarefree).
6//! At a **fixed degree `d`** this is a finite linear-algebra question — is `1` in the `GF(2)`-span of
7//! `{ m · p_C : clause C, monomial m, deg(m·p_C) ≤ d }`? — answered by Gaussian elimination. So degree-`d`
8//! Nullstellensatz is polynomial, and the **degree is the power dial**: `d = 1` recovers parity, larger
9//! `d` reaches counting-style and beyond. The genuinely hard residue (random) needs degree `Θ(n)`, which
10//! is exactly why it stays hard — there is no low-degree algebraic certificate, just as there is no small
11//! symmetry quotient. The two are the same wall seen from two sides.
12//!
13//! Symmetry meets this engine at the monomial basis: an automorphism of the formula permutes monomials,
14//! so the Nullstellensatz system has the family's symmetry and its solution can be sought on the orbit
15//! quotient of the basis — the algebraic form of "decide on the quotient."
16
17use crate::cdcl::Lit;
18use std::collections::{BTreeSet, HashMap, HashSet};
19
20/// A multilinear monomial: the bitmask of the variables it contains (`x² = x` ⟹ squarefree). The `u64`
21/// mask carries up to 63 variables; the *clause* engine's explicit cube enumeration stops at 20, the
22/// degree-bounded polynomial engine ([`monomials_up_to_degree`]) uses the full range.
23pub type Mono = u64;
24/// A multilinear polynomial over `GF(2)`: the set of monomials with coefficient 1 (XOR/symmetric-
25/// difference semantics).
26pub type Poly = BTreeSet<Mono>;
27
28fn toggle(p: &mut Poly, m: Mono) {
29    if !p.remove(&m) {
30        p.insert(m);
31    }
32}
33
34/// `p · m`: multiply a polynomial by a monomial over `GF(2)` (monomials are variable sets, so the
35/// product is the union, and equal products cancel in pairs).
36pub fn poly_mul_mono(p: &Poly, m: Mono) -> Poly {
37    let mut r = Poly::new();
38    for &t in p {
39        toggle(&mut r, t | m); // multilinear product: x·x = x ⟹ OR the masks
40    }
41    r
42}
43
44fn poly_mul(a: &Poly, b: &Poly) -> Poly {
45    let mut r = Poly::new();
46    for &s in a {
47        for &t in b {
48            toggle(&mut r, s | t);
49        }
50    }
51    r
52}
53
54/// The clause polynomial: `1` exactly on the clause's falsifying assignment. The false-indicator of a
55/// positive literal `x` is `1 + x` (`{∅, {x}}`), of a negative literal `¬x` is `x` (`{{x}}`); the clause
56/// polynomial is their product. Degree = clause width.
57pub fn clause_polynomial(clause: &[Lit]) -> Poly {
58    let mut p: Poly = [0u64].into_iter().collect(); // the polynomial "1" (the empty monomial)
59    for l in clause {
60        let bit = 1u64 << l.var();
61        let indicator: Poly = if l.is_positive() {
62            [0u64, bit].into_iter().collect() // 1 + x
63        } else {
64            [bit].into_iter().collect() // x
65        };
66        p = poly_mul(&p, &indicator);
67    }
68    p
69}
70
71/// Is `target` in the `GF(2)`-span of `rows`? Gaussian elimination over packed bit-rows: reduce the rows
72/// to an echelon basis (one pivot bit each), then reduce `target` by it and check it vanishes.
73fn in_gf2_span(mut rows: Vec<Vec<u64>>, target: &[u64]) -> bool {
74    let words = target.len();
75    let high_bit = |r: &[u64]| -> Option<usize> {
76        for w in (0..words).rev() {
77            if r[w] != 0 {
78                return Some(w * 64 + (63 - r[w].leading_zeros() as usize));
79            }
80        }
81        None
82    };
83    let xor_into = |dst: &mut [u64], src: &[u64]| {
84        for w in 0..words {
85            dst[w] ^= src[w];
86        }
87    };
88    // Build an echelon basis keyed by pivot bit.
89    let mut basis: HashMap<usize, Vec<u64>> = HashMap::new();
90    for mut r in rows.drain(..) {
91        while let Some(p) = high_bit(&r) {
92            match basis.get(&p) {
93                Some(b) => xor_into(&mut r, b),
94                None => break,
95            }
96        }
97        if let Some(p) = high_bit(&r) {
98            basis.insert(p, r);
99        }
100    }
101    // Reduce the target.
102    let mut t = target.to_vec();
103    while let Some(p) = high_bit(&t) {
104        match basis.get(&p) {
105            Some(b) => xor_into(&mut t, b),
106            None => break,
107        }
108    }
109    t.iter().all(|&w| w == 0)
110}
111
112/// Does a **degree-`d` Nullstellensatz refutation** exist over `GF(2)`? Sound: such a certificate exists
113/// only when the formula is unsatisfiable. Complete at `d = num_vars` (full degree decides any instance).
114/// Bounded to `num_vars ≤ 20` (the explicit monomial basis).
115pub fn nullstellensatz_refutes(num_vars: usize, clauses: &[Vec<Lit>], degree: usize) -> bool {
116    if num_vars > 20 {
117        return false;
118    }
119    // Monomial basis: every squarefree monomial of degree ≤ `degree`.
120    let mut index: HashMap<Mono, usize> = HashMap::new();
121    for m in 0u64..(1u64 << num_vars) {
122        if m.count_ones() as usize <= degree {
123            let n = index.len();
124            index.insert(m, n);
125        }
126    }
127    let nb = index.len();
128    let words = nb.div_ceil(64).max(1);
129    let to_bits = |p: &Poly| -> Vec<u64> {
130        let mut b = vec![0u64; words];
131        for &m in p {
132            if let Some(&i) = index.get(&m) {
133                b[i / 64] |= 1 << (i % 64);
134            }
135        }
136        b
137    };
138    let monos: Vec<Mono> = index.keys().copied().collect();
139
140    // Generators: m · p_C for every clause C and monomial m with deg(m · p_C) ≤ degree.
141    let mut rows: Vec<Vec<u64>> = Vec::new();
142    for c in clauses {
143        if c.is_empty() {
144            return true; // an empty clause is `1 = 0` outright
145        }
146        let width = c.len();
147        if width > degree {
148            continue;
149        }
150        let pc = clause_polynomial(c);
151        for &m in &monos {
152            if m.count_ones() as usize <= degree - width {
153                rows.push(to_bits(&poly_mul_mono(&pc, m)));
154            }
155        }
156    }
157    // Target: the constant polynomial `1` — the empty monomial.
158    let mut target = vec![0u64; words];
159    let t0 = index[&0u64];
160    target[t0 / 64] |= 1 << (t0 % 64);
161    in_gf2_span(rows, &target)
162}
163
164/// Reduce a polynomial against an echelon basis keyed by leading (largest) monomial: while its leading
165/// monomial is a pivot, XOR (symmetric-difference) that basis row in. The leading monomial strictly
166/// decreases each step, so this terminates; the result is `p` modulo the span.
167fn pc_reduce(basis: &HashMap<Mono, Poly>, mut p: Poly) -> Poly {
168    while let Some(&lm) = p.iter().next_back() {
169        match basis.get(&lm) {
170            Some(b) => {
171                for &m in b {
172                    toggle(&mut p, m);
173                }
174            }
175            None => break,
176        }
177    }
178    p
179}
180
181/// Does a **degree-`d` Polynomial Calculus refutation** exist over `GF(2)`? PC is the *dynamic*
182/// strengthening of Nullstellensatz: start from the clause polynomials and close under (i) `GF(2)` linear
183/// combination and (ii) multiplication by a single variable, keeping every *derived* polynomial
184/// multilinear of degree ≤ `d`; the system is refuted iff the constant `1` is derived. Because an
185/// intermediate linear combination can cancel high-degree terms *before* the next multiply, degree-`d` PC
186/// certifies a superset of what degree-`d` Nullstellensatz can (which must hit each axiom with a single
187/// monomial in one shot). Sound — `1` is derivable only from an unsatisfiable system — and `PC ⊇ NS`, so
188/// it never refutes fewer. Complete at `d = num_vars`. Bounded to `num_vars ≤ 20`.
189pub fn polynomial_calculus_refutes(num_vars: usize, clauses: &[Vec<Lit>], degree: usize) -> bool {
190    if num_vars > 20 {
191        return false;
192    }
193    let poly_deg = |p: &Poly| {
194        p.iter()
195            .map(|&m| m.count_ones() as usize)
196            .max()
197            .unwrap_or(0)
198    };
199    let mut basis: HashMap<Mono, Poly> = HashMap::new();
200    let one: Poly = [0u64].into_iter().collect();
201
202    // Seed the worklist with the clause polynomials usable at this degree (width ≤ d).
203    let mut worklist: Vec<Poly> = Vec::new();
204    for c in clauses {
205        if c.is_empty() {
206            return true; // an empty clause is `1 = 0` outright
207        }
208        if c.len() <= degree {
209            worklist.push(clause_polynomial(c));
210        }
211    }
212    // Saturate: each newly-independent polynomial joins the basis and is multiplied by every variable
213    // (staying within degree), feeding the closure back into the worklist.
214    while let Some(p) = worklist.pop() {
215        let r = pc_reduce(&basis, p);
216        let Some(&lm) = r.iter().next_back() else {
217            continue;
218        }; // reduced to 0 — no new information
219        for i in 0..num_vars as u64 {
220            let q = poly_mul_mono(&r, 1u64 << i);
221            if !q.is_empty() && poly_deg(&q) <= degree {
222                worklist.push(q);
223            }
224        }
225        basis.insert(lm, r);
226        if pc_reduce(&basis, one.clone()).is_empty() {
227            return true; // the constant 1 is in the span — refuted
228        }
229    }
230    false
231}
232
233/// A **constructive Nullstellensatz certificate** over the multilinear `GF(2)` ring: one coefficient
234/// polynomial `g_C` per input clause such that `Σ_C p_C · g_C = 1`, where `p_C = clause_polynomial(C)` is the
235/// clause's false-indicator. The identity is a re-checkable proof of UNSAT — evaluate it at any assignment
236/// `a`: the right side is `1`, so some `p_C(a) = 1`, i.e. *every* assignment falsifies some clause. Where
237/// [`nullstellensatz_refutes`] only *decides* whether such a certificate exists, this one carries the witness.
238#[derive(Clone, Debug)]
239pub struct NsCertificate {
240    num_vars: usize,
241    /// `coeffs[i]` is `g_{C_i}` for the `i`-th input clause (parallel indexing to the clause list).
242    coeffs: Vec<Poly>,
243}
244
245impl NsCertificate {
246    /// The variable count the certificate lives over.
247    pub fn num_vars(&self) -> usize {
248        self.num_vars
249    }
250
251    /// The coefficient polynomials `g_{C_i}` — the witness the certificate carries,
252    /// one per input clause (parallel-indexed to the clause list it was built from).
253    /// Exposes the `Σ_C g_C·p_C = 1` witness for human-readable rendering.
254    pub fn coeffs(&self) -> &[Poly] {
255        &self.coeffs
256    }
257
258    /// The maximum monomial degree among the coefficient polynomials. Multilinear over `num_vars`
259    /// variables, so `≤ num_vars` unconditionally — the content is not this (trivial for a multilinear
260    /// certificate) but that the certificate *exists and is built by one uniform construction at every `n`*.
261    pub fn degree(&self) -> usize {
262        self.coeffs
263            .iter()
264            .flatten()
265            .map(|m| m.count_ones() as usize)
266            .max()
267            .unwrap_or(0)
268    }
269
270    /// **Re-check against the original clauses** (zero trust in the producer): recompute
271    /// `Σ_C clause_polynomial(C) · g_C` and confirm it is the constant `1` (the empty monomial). A `true`
272    /// verdict is an independent proof that `clauses` is unsatisfiable; it fails closed if the certificate's
273    /// clause count does not match the formula it is checked against.
274    pub fn verify(&self, clauses: &[Vec<Lit>]) -> bool {
275        if self.coeffs.len() != clauses.len() {
276            return false;
277        }
278        let mut sum = Poly::new();
279        for (c, g) in clauses.iter().zip(&self.coeffs) {
280            if g.is_empty() {
281                continue;
282            }
283            for m in poly_mul(&clause_polynomial(c), g) {
284                toggle(&mut sum, m);
285            }
286        }
287        sum.len() == 1 && sum.contains(&0u64)
288    }
289}
290
291/// The single-point indicator `δ_a` — the multilinear function that is `1` at assignment `a` and `0` at every
292/// other corner: `Π_{a_i=1} x_i · Π_{a_i=0} (1 + x_i)`. Its monomials are `ones(a) ∪ T` over every subset `T`
293/// of the zero-coordinates (top degree `n`); the `Σ_a δ_a = 1` identity over all corners is the partition of
294/// unity the certificate construction rests on.
295fn point_indicator(a: u64, num_vars: usize) -> Poly {
296    let mask = (1u64 << num_vars).wrapping_sub(1);
297    let ones = a & mask;
298    let zeros = !a & mask;
299    let mut p = Poly::new();
300    let mut sub = zeros;
301    loop {
302        p.insert(ones | sub); // masks are distinct (T ⊆ zeros, disjoint from ones) — no cancellation
303        if sub == 0 {
304            break;
305        }
306        sub = (sub - 1) & zeros;
307    }
308    p
309}
310
311/// **The uniform Nullstellensatz completeness construction.** For any CNF over `num_vars ≤ 20` variables,
312/// return either a constructive [`NsCertificate`] proving UNSAT, or a satisfying assignment proving SAT — a
313/// *total, certifying* decision. The construction is the partition of unity `Σ_a δ_a = 1`: every corner `a`
314/// is charged to one clause it falsifies (a corner that falsifies none *is* a model — SAT), and the
315/// coefficient of clause `C` is `g_C = Σ_{a charged to C} δ_a`. Then `Σ_C p_C · g_C = Σ_a p_{sel(a)} · δ_a =
316/// Σ_a δ_a = 1`, because `p_{sel(a)}(a) = 1` collapses `p·δ_a` to `δ_a` on the cube (multilinear
317/// representations are unique). Because this succeeds *identically at every `n`*, it does not merely measure
318/// but **proves** that every unsatisfiable formula has a degree-`≤ n` `GF(2)` Nullstellensatz refutation — no
319/// minimal-UNSAT family is structureless, at any `n`. This is the census's `max_ns_degree = n` ceiling as a
320/// construction, settling `n = 5, 6, …` where the orbit census is infeasible.
321pub fn build_ns_certificate(
322    num_vars: usize,
323    clauses: &[Vec<Lit>],
324) -> Result<NsCertificate, Vec<bool>> {
325    assert!(
326        num_vars <= 20,
327        "the explicit-corner construction is bounded to num_vars ≤ 20"
328    );
329    let mut coeffs: Vec<Poly> = vec![Poly::new(); clauses.len()];
330    for a in 0u64..(1u64 << num_vars) {
331        let sel = clauses.iter().position(|c| {
332            !c.iter()
333                .any(|l| ((a >> l.var()) & 1 == 1) == l.is_positive())
334        });
335        match sel {
336            None => return Err((0..num_vars).map(|i| (a >> i) & 1 == 1).collect()),
337            Some(ci) => {
338                for m in point_indicator(a, num_vars) {
339                    toggle(&mut coeffs[ci], m);
340                }
341            }
342        }
343    }
344    Ok(NsCertificate { num_vars, coeffs })
345}
346
347/// The closure of a permutation group under composition (BFS), for small groups. Elements keyed by their
348/// image vector so the group is deduplicated.
349pub fn close_perm_group(gens: &[crate::proof::Perm], num_vars: usize) -> Vec<crate::proof::Perm> {
350    use crate::proof::Perm;
351    let key = |p: &Perm| -> Vec<u32> {
352        (0..num_vars)
353            .map(|v| p.apply(Lit::pos(v as u32)).var())
354            .collect()
355    };
356    let id = Perm::identity(num_vars);
357    let mut seen: std::collections::BTreeSet<Vec<u32>> = [key(&id)].into_iter().collect();
358    let mut group = vec![id.clone()];
359    let mut frontier = vec![id];
360    while let Some(p) = frontier.pop() {
361        for g in gens {
362            let q = p.compose(g);
363            if seen.insert(key(&q)) {
364                group.push(q.clone());
365                frontier.push(q);
366            }
367        }
368    }
369    group
370}
371
372/// The **symmetrization** of a `GF(2)` functional `L` (given as the monomials where it is `1`) over a group:
373/// `Σ_{g∈G} g·L` (mod 2). The Reynolds/averaging operator of characteristic 0 — but *without the `1/|G|`*,
374/// because that division is unavailable over `GF(2)`.
375fn symmetrize(l: &[Mono], group: &[crate::proof::Perm]) -> BTreeSet<Mono> {
376    let mut sym: BTreeSet<Mono> = BTreeSet::new();
377    for &m in l {
378        for g in group {
379            let img = apply_perm_to_mono(g, m);
380            if !sym.remove(&img) {
381                sym.insert(img);
382            }
383        }
384    }
385    sym
386}
387
388/// Exact binomial coefficient `C(n, k)` in `u128` (small `n`; the running-product form stays integral).
389fn binom(n: usize, k: usize) -> u128 {
390    if k > n {
391        return 0;
392    }
393    let k = k.min(n - k);
394    let mut c = 1u128;
395    for i in 0..k {
396        c = c * (n - i) as u128 / (i + 1) as u128;
397    }
398    c
399}
400
401/// The width of the degree-`d` Nullstellensatz system over `n` variables: the count of multilinear monomials
402/// of degree `≤ d`, `Σ_{k≤d} C(n,k)`. At `d = n` this is exactly `2ⁿ` — so the degree-`n` certificate that
403/// [`build_ns_certificate`] always produces (completeness: no unsatisfiable formula over `n` variables is
404/// "structureless") lives in an **exponentially large** space. The certificate's *existence* is an
405/// information-theoretic fact about the finite cube; it is not an efficient algorithm, and it says nothing
406/// about P vs NP — which is a statement about the asymptotic growth of a *family* of instances, not any fixed
407/// finite `n` (a fixed finite problem is decidable by table lookup, vacuously).
408pub fn nullstellensatz_basis_size(n: usize, d: usize) -> u128 {
409    (0..=d.min(n)).map(|k| binom(n, k)).sum()
410}
411
412/// All squarefree monomials of degree `≤ degree` over `num_vars ≤ 63` variables, ascending as `u64`s —
413/// enumerated directly (Gosper's next-`k`-subset walk per degree class), never touching the `2ⁿ` cube.
414/// This is the basis walk that lifts fixed-degree Nullstellensatz work past the clause engine's
415/// 20-variable cap: the count is `Σ_{k≤d} C(n,k)` ([`nullstellensatz_basis_size`]), not `2ⁿ`.
416pub fn monomials_up_to_degree(num_vars: usize, degree: usize) -> Vec<Mono> {
417    assert!(
418        num_vars <= 63,
419        "the u64 monomial mask carries ≤ 63 variables"
420    );
421    let mut out: Vec<Mono> = vec![0];
422    for k in 1..=degree.min(num_vars) {
423        let limit: Mono = 1u64 << num_vars;
424        let mut m: Mono = (1u64 << k) - 1; // the least k-subset
425        while m < limit {
426            out.push(m);
427            let c = m & m.wrapping_neg(); // Gosper's hack: next integer with the same popcount
428            let r = m + c;
429            m = (((r ^ m) >> 2) / c) | r;
430        }
431    }
432    out.sort_unstable();
433    out
434}
435
436/// The degree of a multilinear `GF(2)` polynomial: its largest monomial's popcount (`0` for the zero
437/// polynomial and for the constant `1`).
438pub fn poly_degree(p: &Poly) -> usize {
439    p.iter()
440        .map(|&m| m.count_ones() as usize)
441        .max()
442        .unwrap_or(0)
443}
444
445/// Does a **degree-`d` Nullstellensatz refutation** exist over `GF(2)` for an arbitrary polynomial
446/// generator system — is `1` in the `GF(2)`-span of `{ m·g : deg(m·g) ≤ d }`? The clause engine's
447/// question asked of *any* generators, not just clause polynomials: the substrate for the linear
448/// encoding ([`exactly_one_linear_generators`]) and the symmetric-family machinery. The multiplier rule
449/// is exact — a product is admitted by its degree *after* multilinear collapse. (For clause polynomials
450/// this span equals the clause engine's: a multiplier overlapping a positive literal kills the product,
451/// one overlapping a negative literal absorbs into a smaller multiplier — pinned by the differential
452/// test.) Degree-bounded enumeration, so it scales to `num_vars ≤ 63`.
453pub fn ns_refutes_polys(num_vars: usize, gens: &[Poly], degree: usize) -> bool {
454    let basis = monomials_up_to_degree(num_vars, degree);
455    let index: HashMap<Mono, usize> = basis.iter().enumerate().map(|(i, &m)| (m, i)).collect();
456    let words = basis.len().div_ceil(64).max(1);
457    let to_bits = |p: &Poly| -> Vec<u64> {
458        let mut b = vec![0u64; words];
459        for &m in p {
460            if let Some(&i) = index.get(&m) {
461                b[i / 64] |= 1 << (i % 64);
462            }
463        }
464        b
465    };
466    let mut rows: Vec<Vec<u64>> = Vec::new();
467    for g in gens {
468        if g.is_empty() {
469            continue; // the zero polynomial generates nothing
470        }
471        for &m in &basis {
472            let prod = poly_mul_mono(g, m);
473            if !prod.is_empty() && poly_degree(&prod) <= degree {
474                rows.push(to_bits(&prod));
475            }
476        }
477    }
478    let t0 = index[&0u64];
479    let mut target = vec![0u64; words];
480    target[t0 / 64] |= 1 << (t0 % 64);
481    in_gf2_span(rows, &target)
482}
483
484/// [`ns_lower_bound_witness`] for an arbitrary polynomial generator system: a degree-`d`
485/// pseudo-expectation `L` with `L(1) = 1` and `L(m·g) = 0` for every admitted generator, returned as the
486/// monomials where `L = 1`. `Some(L)` certifies `NS-degree > d` for the system (re-checkable by
487/// [`check_ns_lower_bound_polys`], zero trust in the solver); `None` means a degree-`d` refutation
488/// exists. Degree-bounded enumeration — `num_vars ≤ 63`.
489pub fn ns_lower_bound_witness_polys(
490    num_vars: usize,
491    gens: &[Poly],
492    degree: usize,
493) -> Option<Vec<Mono>> {
494    let basis = monomials_up_to_degree(num_vars, degree);
495    let index: HashMap<Mono, usize> = basis.iter().enumerate().map(|(i, &m)| (m, i)).collect();
496    let nb = basis.len();
497    let words = nb.div_ceil(64).max(1);
498    let mask_of = |p: &Poly| -> Vec<u64> {
499        let mut mask = vec![0u64; words];
500        for &m in p {
501            if let Some(&i) = index.get(&m) {
502                mask[i / 64] |= 1u64 << (i % 64);
503            }
504        }
505        mask
506    };
507    let mut eqs: Vec<(Vec<u64>, bool)> = Vec::new();
508    for g in gens {
509        if g.is_empty() {
510            continue;
511        }
512        for &m in &basis {
513            let prod = poly_mul_mono(g, m);
514            if !prod.is_empty() && poly_degree(&prod) <= degree {
515                eqs.push((mask_of(&prod), false)); // ⟨L, m·g⟩ = 0
516            }
517        }
518    }
519    let t0 = index[&0u64];
520    let mut target = vec![0u64; words];
521    target[t0 / 64] |= 1u64 << (t0 % 64);
522    eqs.push((target, true)); // L(1) = 1
523    let l = gf2_solve(&eqs, nb)?;
524    Some(
525        (0..nb)
526            .filter(|&i| (l[i / 64] >> (i % 64)) & 1 == 1)
527            .map(|i| basis[i])
528            .collect(),
529    )
530}
531
532/// [`ns_lower_bound_witness_polys`] restricted to a **sub-basis**: the functional `L` is sought only on
533/// monomials passing `in_basis` (`L = 0` elsewhere), while the constraints `⟨L, m·g⟩ = 0` still range
534/// over *all* admitted generators — so any `Some` is a fully valid,
535/// [`check_ns_lower_bound_polys`]-verifiable witness, and `None` means only "no witness on this
536/// sub-basis". The structure probe: which candidate supports carry a family's lower bound (for
537/// pigeonhole this is how the hole-injective support was found and the classical partial-matching
538/// support was ruled out over `GF(2)`). Degree-bounded enumeration — `num_vars ≤ 63`.
539pub fn ns_lower_bound_witness_polys_on_basis(
540    num_vars: usize,
541    gens: &[Poly],
542    degree: usize,
543    in_basis: &dyn Fn(Mono) -> bool,
544) -> Option<Vec<Mono>> {
545    let all = monomials_up_to_degree(num_vars, degree);
546    let basis: Vec<Mono> = all.iter().copied().filter(|&m| in_basis(m)).collect();
547    let index: HashMap<Mono, usize> = basis.iter().enumerate().map(|(i, &m)| (m, i)).collect();
548    index.get(&0u64)?; // the empty monomial must be in the sub-basis for L(1) = 1
549    let nb = basis.len();
550    let words = nb.div_ceil(64).max(1);
551    let mask_of = |p: &Poly| -> Vec<u64> {
552        let mut mask = vec![0u64; words];
553        for &m in p {
554            if let Some(&i) = index.get(&m) {
555                mask[i / 64] |= 1u64 << (i % 64);
556            }
557        }
558        mask
559    };
560    let mut eqs: Vec<(Vec<u64>, bool)> = Vec::new();
561    for g in gens {
562        if g.is_empty() {
563            continue;
564        }
565        for &m in &all {
566            let prod = poly_mul_mono(g, m);
567            if !prod.is_empty() && poly_degree(&prod) <= degree {
568                eqs.push((mask_of(&prod), false));
569            }
570        }
571    }
572    let t0 = index[&0u64];
573    let mut target = vec![0u64; words];
574    target[t0 / 64] |= 1u64 << (t0 % 64);
575    eqs.push((target, true));
576    let l = gf2_solve(&eqs, nb)?;
577    Some(
578        (0..nb)
579            .filter(|&i| (l[i / 64] >> (i % 64)) & 1 == 1)
580            .map(|i| basis[i])
581            .collect(),
582    )
583}
584
585/// Re-check a [`ns_lower_bound_witness_polys`] certificate (zero trust in the producer): `L(1) = 1` and
586/// `L(m·g) = 0` for every admitted generator of the system. `true` ⟹ the generator system genuinely has
587/// no degree-`d` `GF(2)` Nullstellensatz refutation. Degree-bounded enumeration — `num_vars ≤ 63`.
588pub fn check_ns_lower_bound_polys(
589    num_vars: usize,
590    gens: &[Poly],
591    degree: usize,
592    witness: &[Mono],
593) -> bool {
594    let l: BTreeSet<Mono> = witness.iter().copied().collect();
595    if !l.contains(&0u64) {
596        return false; // L(1) must be 1
597    }
598    let basis = monomials_up_to_degree(num_vars, degree);
599    for g in gens {
600        if g.is_empty() {
601            continue;
602        }
603        for &m in &basis {
604            let prod = poly_mul_mono(g, m);
605            if !prod.is_empty()
606                && poly_degree(&prod) <= degree
607                && prod.iter().filter(|t| l.contains(t)).count() % 2 == 1
608            {
609                return false; // ⟨L, m·g⟩ must be 0
610            }
611        }
612    }
613    true
614}
615
616/// The **linear encoding** of exactly-one constraints: for each group `G` the degree-1 generator
617/// `1 + Σ_{v∈G} x_v` (the `GF(2)` form of `Σ x = 1`) plus the pairwise products `x_u·x_v` over each
618/// group, deduplicated. This is the encoding under which the modular-counting and pigeonhole degree
619/// lower bounds are stated in the literature — the wide at-least-one clause is recovered from it modulo
620/// the pairs (the interreduction test pins the identity, and the clause→linear direction is
621/// degree-preserving, so bounds against this encoding are the stronger statements). The linear
622/// generators come first (one per group, in group order), then the pairs.
623pub fn exactly_one_linear_generators(groups: &[Vec<u32>]) -> Vec<Poly> {
624    let mut gens: Vec<Poly> = Vec::new();
625    for g in groups {
626        let mut lin: Poly = [0u64].into_iter().collect();
627        for &v in g {
628            assert!(v < 63, "the u64 monomial mask carries ≤ 63 variables");
629            toggle(&mut lin, 1u64 << v);
630        }
631        gens.push(lin);
632    }
633    let mut pairs: BTreeSet<Mono> = BTreeSet::new();
634    for g in groups {
635        for (i, &u) in g.iter().enumerate() {
636            for &v in &g[i + 1..] {
637                pairs.insert((1u64 << u) | (1u64 << v));
638            }
639        }
640    }
641    gens.extend(pairs.into_iter().map(|m| [m].into_iter().collect::<Poly>()));
642    gens
643}
644
645/// Solve a `GF(2)` linear system `⟨x, coeffᵢ⟩ = rhsᵢ` (each `coeff` a multi-word bit-vector over `nvars`
646/// variables) by Gaussian elimination to reduced row echelon form. Returns any solution `x` (bit-packed into
647/// `⌈nvars/64⌉` words) or `None` if the system is inconsistent. Multi-word, so it scales past 63 variables.
648pub fn gf2_solve(equations: &[(Vec<u64>, bool)], nvars: usize) -> Option<Vec<u64>> {
649    let words = nvars.div_ceil(64).max(1);
650    let bit = |v: &[u64], i: usize| (v[i / 64] >> (i % 64)) & 1 == 1;
651    let mut rows: Vec<(Vec<u64>, bool)> = equations.to_vec();
652    let mut pivots: Vec<usize> = Vec::new();
653    let mut r = 0usize;
654    for col in 0..nvars {
655        let Some(sel) = (r..rows.len()).find(|&i| bit(&rows[i].0, col)) else {
656            continue;
657        };
658        rows.swap(r, sel);
659        let (pmask, prhs) = (rows[r].0.clone(), rows[r].1);
660        for i in 0..rows.len() {
661            if i != r && bit(&rows[i].0, col) {
662                for w in 0..words {
663                    rows[i].0[w] ^= pmask[w];
664                }
665                rows[i].1 ^= prhs;
666            }
667        }
668        pivots.push(col);
669        r += 1;
670    }
671    if rows.iter().any(|(m, b)| *b && m.iter().all(|&w| w == 0)) {
672        return None; // 0 = 1 — inconsistent
673    }
674    // RREF: each pivot row's only set bits are its pivot column plus free columns; free vars = 0 ⟹ x_col = rhs.
675    let mut x = vec![0u64; words];
676    for (i, &col) in pivots.iter().enumerate() {
677        if rows[i].1 {
678            x[col / 64] |= 1u64 << (col % 64);
679        }
680    }
681    Some(x)
682}
683
684/// **A re-checkable degree-`d` Nullstellensatz LOWER-bound certificate.** Where [`nullstellensatz_refutes`]
685/// *decides* whether a degree-`d` refutation exists, this witnesses its NON-existence: a `GF(2)` linear
686/// functional `L` on the degree-`≤ d` monomials (a *degree-`d` pseudo-expectation`) with `L(1) = 1` and
687/// `L(m · p_C) = 0` for every generator. Such an `L` exists iff `1` is **not** in the `GF(2)`-span of the
688/// generators, i.e. iff there is no degree-`d` refutation — so `Some(L)` certifies the lower bound
689/// `NS-degree(F) > d`, independently re-checkable by [`check_ns_lower_bound`] (no trust in the solver). The
690/// certificate is returned as the list of monomials on which `L` is `1`. `None` means a degree-`d` refutation
691/// exists (no lower bound at `d`). Multi-word linear algebra, so the monomial basis is not size-capped —
692/// only `num_vars ≤ 20` for the explicit basis enumeration.
693pub fn ns_lower_bound_witness(
694    num_vars: usize,
695    clauses: &[Vec<Lit>],
696    degree: usize,
697) -> Option<Vec<u64>> {
698    if num_vars > 20 {
699        return None;
700    }
701    let mut index: HashMap<Mono, usize> = HashMap::new();
702    let mut monos: Vec<Mono> = Vec::new();
703    for m in 0u64..(1u64 << num_vars) {
704        if m.count_ones() as usize <= degree {
705            index.insert(m, monos.len());
706            monos.push(m);
707        }
708    }
709    let nb = monos.len();
710    let words = nb.div_ceil(64).max(1);
711    let mask_of = |p: &Poly| -> Vec<u64> {
712        let mut mask = vec![0u64; words];
713        for &m in p {
714            if let Some(&i) = index.get(&m) {
715                mask[i / 64] |= 1u64 << (i % 64);
716            }
717        }
718        mask
719    };
720    let mut eqs: Vec<(Vec<u64>, bool)> = Vec::new();
721    for c in clauses {
722        let width = c.len();
723        if width == 0 {
724            return None; // an empty clause is an immediate refutation — no lower bound
725        }
726        if width > degree {
727            continue;
728        }
729        let pc = clause_polynomial(c);
730        for &m in &monos {
731            if m.count_ones() as usize <= degree - width {
732                eqs.push((mask_of(&poly_mul_mono(&pc, m)), false)); // ⟨L, m·p_C⟩ = 0
733            }
734        }
735    }
736    let t0 = index[&0u64];
737    let mut target = vec![0u64; words];
738    target[t0 / 64] |= 1u64 << (t0 % 64);
739    eqs.push((target, true)); // L(1) = 1
740    let l = gf2_solve(&eqs, nb)?;
741    Some(
742        (0..nb)
743            .filter(|&i| (l[i / 64] >> (i % 64)) & 1 == 1)
744            .map(|i| monos[i])
745            .collect(),
746    )
747}
748
749/// [`ns_lower_bound_witness`] restricted to a **sub-basis** of monomials: the functional `L` is sought only
750/// on monomials `m` with `in_basis(m)` (and `L = 0` elsewhere), while the constraints `⟨L, m·p_C⟩ = 0` still
751/// range over *all* generators. `Some(L)` is a fully valid, `check_ns_lower_bound`-verifiable witness (the
752/// restriction only limits the *search*, not the check); `None` here means "no witness on this sub-basis" —
753/// which, unlike the full-basis version, does **not** imply a refutation exists. This exposes the *structure*
754/// of a lower bound: e.g. for pigeonhole, the partial-matching sub-basis already carries the certificate.
755pub fn ns_lower_bound_witness_on_basis(
756    num_vars: usize,
757    clauses: &[Vec<Lit>],
758    degree: usize,
759    in_basis: &dyn Fn(Mono) -> bool,
760) -> Option<Vec<u64>> {
761    if num_vars > 20 {
762        return None;
763    }
764    let mut index: HashMap<Mono, usize> = HashMap::new();
765    let mut basis: Vec<Mono> = Vec::new();
766    for m in 0u64..(1u64 << num_vars) {
767        if m.count_ones() as usize <= degree && in_basis(m) {
768            index.insert(m, basis.len());
769            basis.push(m);
770        }
771    }
772    index.get(&0u64)?; // the empty monomial must be in the basis for L(1) = 1
773    let nb = basis.len();
774    let words = nb.div_ceil(64).max(1);
775    let mask_of = |p: &Poly| -> Vec<u64> {
776        let mut mask = vec![0u64; words];
777        for &m in p {
778            if let Some(&i) = index.get(&m) {
779                mask[i / 64] |= 1u64 << (i % 64);
780            }
781        }
782        mask
783    };
784    let mults: Vec<Mono> = (0u64..(1u64 << num_vars))
785        .filter(|m| m.count_ones() as usize <= degree)
786        .collect();
787    let mut eqs: Vec<(Vec<u64>, bool)> = Vec::new();
788    for c in clauses {
789        let width = c.len();
790        if width == 0 {
791            return None;
792        }
793        if width > degree {
794            continue;
795        }
796        let pc = clause_polynomial(c);
797        for &m in &mults {
798            if m.count_ones() as usize <= degree - width {
799                eqs.push((mask_of(&poly_mul_mono(&pc, m)), false));
800            }
801        }
802    }
803    let t0 = index[&0u64];
804    let mut target = vec![0u64; words];
805    target[t0 / 64] |= 1u64 << (t0 % 64);
806    eqs.push((target, true));
807    let l = gf2_solve(&eqs, nb)?;
808    Some(
809        (0..nb)
810            .filter(|&i| (l[i / 64] >> (i % 64)) & 1 == 1)
811            .map(|i| basis[i])
812            .collect(),
813    )
814}
815
816/// Is a `PHP` monomial a **partial matching** — an injective partial pigeon→hole map? PHP's variable
817/// `x_{p,h}` sits at index `p·holes + h` ([`crate::families::php`]), so a monomial (a set of variables) is a
818/// partial matching iff no two of its variables share a pigeon or a hole. This is the support of the
819/// Razborov degree lower bound's pseudo-expectation.
820pub fn php_is_partial_matching(mono: Mono, holes: usize) -> bool {
821    let (mut pigeons, mut used_holes) = (0u64, 0u64);
822    let mut bits = mono;
823    while bits != 0 {
824        let v = bits.trailing_zeros() as usize;
825        let (p, h) = (v / holes, v % holes);
826        if (pigeons >> p) & 1 == 1 || (used_holes >> h) & 1 == 1 {
827            return false;
828        }
829        pigeons |= 1u64 << p;
830        used_holes |= 1u64 << h;
831        bits &= bits - 1;
832    }
833    true
834}
835
836/// Is a `PHP` monomial **hole-injective** — no two of its edges share a hole? Standard PHP forbids two
837/// pigeons in one hole but allows a pigeon in several holes, so the at-most-one clauses force the `GF(2)`
838/// pseudo-expectation to vanish exactly on hole-*collision* monomials — i.e. its support lies in the
839/// hole-injective monomials (partial functions hole→pigeon). This is looser than a partial matching (which
840/// also forbids pigeon repeats) and is the correct `GF(2)` support.
841pub fn php_is_hole_injective(mono: Mono, holes: usize) -> bool {
842    let mut used_holes = 0u64;
843    let mut bits = mono;
844    while bits != 0 {
845        let h = (bits.trailing_zeros() as usize) % holes;
846        if (used_holes >> h) & 1 == 1 {
847            return false;
848        }
849        used_holes |= 1u64 << h;
850        bits &= bits - 1;
851    }
852    true
853}
854
855/// Re-check a [`ns_lower_bound_witness`] certificate (zero trust in the producer): the functional `L` (given
856/// as the monomials on which it is `1`) must satisfy `L(1) = 1` and `L(m · p_C) = 0` for every degree-`≤ d`
857/// generator. `true` ⟹ `F` genuinely has no degree-`d` `GF(2)` Nullstellensatz refutation.
858pub fn check_ns_lower_bound(
859    num_vars: usize,
860    clauses: &[Vec<Lit>],
861    degree: usize,
862    witness: &[u64],
863) -> bool {
864    let l: BTreeSet<Mono> = witness.iter().copied().collect();
865    let pairs = |p: &Poly| -> bool { p.iter().filter(|m| l.contains(m)).count() % 2 == 1 }; // ⟨L, p⟩
866    if !l.contains(&0u64) {
867        return false; // L(1) must be 1
868    }
869    for c in clauses {
870        let width = c.len();
871        if width == 0 {
872            return false;
873        }
874        if width > degree {
875            continue;
876        }
877        let pc = clause_polynomial(c);
878        for m in 0u64..(1u64 << num_vars) {
879            if m.count_ones() as usize <= degree.saturating_sub(width) {
880                if pairs(&poly_mul_mono(&pc, m)) {
881                    return false; // ⟨L, m·p_C⟩ must be 0
882                }
883            }
884        }
885    }
886    true
887}
888
889/// The **atom** of the partition-of-unity recurrence on variable `v`: `(1 + x_v) + x_v`, which reduces to
890/// the constant `1` in the multilinear `GF(2)` ring (`x_v + x_v = 0`). This single identity is the engine of
891/// the whole `n = ∞` ratchet: it is *independent of `n`*, so a product of `n` copies of it is `1` at every
892/// scale.
893pub fn pou_atom(v: usize) -> Poly {
894    let x: Poly = [1u64 << v].into_iter().collect();
895    let one_plus_x: Poly = [0u64, 1u64 << v].into_iter().collect();
896    let mut atom = one_plus_x;
897    for m in x {
898        toggle(&mut atom, m);
899    }
900    atom
901}
902
903/// The **partition of unity** over the `n`-cube: `Σ_{a ∈ {0,1}ⁿ} δ_a`, the sum of every corner's
904/// point-indicator. It is the constant `1` for all `n` — the identity the constructive Nullstellensatz
905/// certificate ([`build_ns_certificate`]) rests on. Computed here by direct summation (for finite checks);
906/// [`pou_as_product`] gives the closed form that proves it `∀n`.
907pub fn partition_of_unity(n: usize) -> Poly {
908    let mut sum = Poly::new();
909    for a in 0..(1u64 << n) {
910        for m in point_indicator(a, n) {
911            toggle(&mut sum, m);
912        }
913    }
914    sum
915}
916
917/// The **closed form** of the partition of unity: the product `Π_{v<n} ((1+x_v) + x_v)` of the per-coordinate
918/// atoms. By distributivity `Σ_a Π_i f_{i,a_i} = Π_i (f_{i,0} + f_{i,1})`, this equals
919/// [`partition_of_unity`] — a *sum of `2ⁿ` products* rewritten as a *product of `n` sums*. Since every atom
920/// is `1` ([`pou_atom`]), the product is `1` for **every** `n`. This is the ratchet to `n = ∞`: not `2ⁿ`
921/// terms checked one cube at a time, but `n` identical unit factors.
922pub fn pou_as_product(n: usize) -> Poly {
923    let mut product: Poly = [0u64].into_iter().collect(); // the polynomial 1
924    for v in 0..n {
925        product = poly_mul(&product, &pou_atom(v));
926    }
927    product
928}
929
930/// Apply a formula automorphism to a monomial: a monomial is a *set of variables*, so the permutation
931/// part of `σ` relabels them (phase flips do not act on monomials). The bridge from the symmetry group
932/// to the polynomial basis.
933pub fn apply_perm_to_mono(perm: &crate::proof::Perm, m: Mono) -> Mono {
934    let mut out = 0u64;
935    for v in 0..perm.num_vars() {
936        if m & (1 << v) != 0 {
937            out |= 1 << perm.apply(Lit::pos(v as u32)).var();
938        }
939    }
940    out
941}
942
943/// **Symmetry-break Polynomial Calculus at the basis.** Partition the degree-≤`degree` monomials into
944/// orbits under the formula's automorphisms. The orbit count is the width of the *symmetry-reduced*
945/// Nullstellensatz system — a symmetric certificate is constant on each orbit, so the Gaussian runs over
946/// the quotient instead of all `C(n,d)` monomials. The same collapse that made the field cuts O(1),
947/// inherited by the algebraic engine. (Bounded to `num_vars ≤ 20`.)
948pub fn monomial_orbits(
949    num_vars: usize,
950    degree: usize,
951    generators: &[crate::proof::Perm],
952) -> Vec<Vec<Mono>> {
953    let basis: BTreeSet<Mono> = (0u64..(1u64 << num_vars))
954        .filter(|m| m.count_ones() as usize <= degree)
955        .collect();
956    let mut seen: BTreeSet<Mono> = BTreeSet::new();
957    let mut orbits = Vec::new();
958    for &m in &basis {
959        if seen.contains(&m) {
960            continue;
961        }
962        let mut orbit = BTreeSet::new();
963        orbit.insert(m);
964        let mut stack = vec![m];
965        while let Some(x) = stack.pop() {
966            for g in generators {
967                let y = apply_perm_to_mono(g, x);
968                if basis.contains(&y) && orbit.insert(y) {
969                    stack.push(y);
970                }
971            }
972        }
973        for &x in &orbit {
974            seen.insert(x);
975        }
976        orbits.push(orbit.into_iter().collect());
977    }
978    orbits
979}
980
981/// The generators of the full symmetric group `Sₙ` on `n` variables: the adjacent transpositions
982/// `(i, i+1)`. `Sₙ` is the symmetry of a *fully-symmetric* formula (every variable interchangeable), and
983/// under it the monomial basis collapses to one orbit per degree — the sharpest instance of
984/// [`monomial_orbits`]' compression.
985pub fn symmetric_group_generators(n: usize) -> Vec<crate::proof::Perm> {
986    (0..n.saturating_sub(1))
987        .map(|i| {
988            let images: Vec<Lit> = (0..n)
989                .map(|v| {
990                    if v == i {
991                        Lit::pos((i + 1) as u32)
992                    } else if v == i + 1 {
993                        Lit::pos(i as u32)
994                    } else {
995                        Lit::pos(v as u32)
996                    }
997                })
998                .collect();
999            crate::proof::Perm::from_images(images)
1000        })
1001        .collect()
1002}
1003
1004/// **Symmetry-reduced Nullstellensatz** — the algebraic refutation collapsed by the formula's symmetry.
1005/// Full degree-`d` NS asks whether `1` lies in the `GF(2)`-span of the generators `m·p_C`, a Gaussian over
1006/// up to `C(n,≤d)` monomial columns. When the formula has a symmetry group `G`, summing each generator's
1007/// `G`-orbit gives an *invariant* generator, and every invariant polynomial is constant on the monomial
1008/// orbits ([`monomial_orbits`]) — so the same span check runs over just `#orbits` columns and
1009/// `#generator-orbits` rows. For a symmetric family that is the difference between `2^Θ(n)` and `O(1)`.
1010///
1011/// **Sound**: each row is an honest `GF(2)`-sum of NS generators, so `1` in the reduced span is `1` in the
1012/// full span — a real refutation, hence UNSAT. Incomplete (a refutation need not be `G`-invariant), and
1013/// fail-closed: if a passed generator is not a genuine symmetry (an orbit step leaves the generator set)
1014/// it declines rather than reduce unsoundly. `generators` must be automorphisms of `clauses`.
1015pub fn nullstellensatz_refutes_symmetric(
1016    num_vars: usize,
1017    clauses: &[Vec<Lit>],
1018    degree: usize,
1019    generators: &[crate::proof::Perm],
1020) -> bool {
1021    if num_vars > 20 {
1022        return false;
1023    }
1024    // Monomial orbits give the reduced column basis; an invariant polynomial is all-or-nothing per orbit.
1025    let mono_orbits = monomial_orbits(num_vars, degree, generators);
1026    let n_orbits = mono_orbits.len();
1027    let words = n_orbits.div_ceil(64).max(1);
1028    let orbit_index: HashMap<Mono, usize> = (0u64..(1u64 << num_vars))
1029        .filter(|m| m.count_ones() as usize <= degree)
1030        .map(|m| (m, mono_orbits.iter().position(|o| o.contains(&m)).unwrap()))
1031        .collect();
1032    let to_orbit_bits = |p: &Poly| -> Vec<u64> {
1033        let mut b = vec![0u64; words];
1034        for (oi, orbit) in mono_orbits.iter().enumerate() {
1035            if p.contains(&orbit[0]) {
1036                b[oi / 64] |= 1 << (oi % 64);
1037            }
1038        }
1039        b
1040    };
1041    let apply_sigma = |sigma: &crate::proof::Perm, p: &Poly| -> Poly {
1042        let mut out = Poly::new();
1043        for &m in p {
1044            toggle(&mut out, apply_perm_to_mono(sigma, m));
1045        }
1046        out
1047    };
1048    let canon = |p: &Poly| -> Vec<Mono> { p.iter().copied().collect() };
1049
1050    // The NS generators m·p_C with deg(m·p_C) ≤ degree.
1051    let monos: Vec<Mono> = orbit_index.keys().copied().collect();
1052    let mut gens: Vec<Poly> = Vec::new();
1053    for c in clauses {
1054        if c.is_empty() {
1055            return true; // an empty clause is `1 = 0`
1056        }
1057        let width = c.len();
1058        if width > degree {
1059            continue;
1060        }
1061        let pc = clause_polynomial(c);
1062        for &m in &monos {
1063            if m.count_ones() as usize <= degree - width {
1064                gens.push(poly_mul_mono(&pc, m));
1065            }
1066        }
1067    }
1068    let gen_set: HashSet<Vec<Mono>> = gens.iter().map(|p| canon(p)).collect();
1069
1070    // Sum each generator-orbit into an invariant generator; express it in the orbit basis.
1071    let mut seen: HashSet<Vec<Mono>> = HashSet::new();
1072    let mut rows: Vec<Vec<u64>> = Vec::new();
1073    for g in &gens {
1074        if seen.contains(&canon(g)) {
1075            continue;
1076        }
1077        let mut orbit_sum = Poly::new();
1078        let mut local: HashSet<Vec<Mono>> = HashSet::from([canon(g)]);
1079        let mut stack = vec![g.clone()];
1080        while let Some(x) = stack.pop() {
1081            seen.insert(canon(&x));
1082            for &m in &x {
1083                toggle(&mut orbit_sum, m);
1084            }
1085            for sigma in generators {
1086                let y = apply_sigma(sigma, &x);
1087                let yk = canon(&y);
1088                if !gen_set.contains(&yk) {
1089                    return false; // not a genuine symmetry of the NS system — fail closed
1090                }
1091                if local.insert(yk) {
1092                    stack.push(y);
1093                }
1094            }
1095        }
1096        rows.push(to_orbit_bits(&orbit_sum));
1097    }
1098
1099    // Target: the constant `1` (the empty monomial, its own orbit).
1100    let mut target = vec![0u64; words];
1101    if let Some(&oi) = orbit_index.get(&0u64) {
1102        target[oi / 64] |= 1 << (oi % 64);
1103    }
1104    in_gf2_span(rows, &target)
1105}
1106
1107#[cfg(test)]
1108#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/polycalc/tests.rs"]
1109mod tests;