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;