Skip to main content

vela_verify/
lib.rs

1//! Frozen, independent exact verifiers for combinatorial and
2//! coding-theory witnesses.
3//!
4//! The discovery loop's proposers are **untrusted**: an agent returns an
5//! explicit construction (a set of points, a ruler, a generator matrix),
6//! and this crate re-checks it deterministically before any claim is
7//! recorded. A witness that does not pass here is discarded no matter
8//! what the proposer reported. Corrupting a witness must fail the
9//! verifier — that is the property the self-tests pin.
10//!
11//! This is the reference verifier registry the trust gate
12//! ([`vela_protocol::verifier_attachment`]) and `vela reproduce` build
13//! on: a passing verify here is the *evidence* an `exact_construction`
14//! verifier attachment attests to. The verifiers are intentionally
15//! dependency-light (serde only) and pure — no I/O, no randomness — so a
16//! third party can re-run them and get byte-identical verdicts.
17//!
18//! Ported from the campaign's `scripts/verify_construction.py`; the
19//! Python reference and this Rust port must agree on every witness.
20
21use std::collections::HashSet;
22
23use serde::{Deserialize, Serialize};
24
25/// A stable, reproducible identity for the frozen verifier build, recorded in
26/// the `policy.auto_admitted` audit record (`verifier_env_hash`) so an auditor
27/// can pin which frozen `vela-verify` produced a machine admission. Same source
28/// + same release => same string.
29pub const ENV_ID: &str = concat!("vela-verify@", env!("CARGO_PKG_VERSION"));
30
31/// The outcome of verifying one witness.
32#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
33pub struct VerifyResult {
34    /// Whether the witness passed its exact verifier.
35    pub ok: bool,
36    /// Human-readable detail (what was checked, or why it failed).
37    pub message: String,
38    /// A recomputed numeric quantity for "value-to-beat" problems
39    /// (currently unused by the boolean verifiers; reserved).
40    #[serde(default, skip_serializing_if = "Option::is_none")]
41    pub value: Option<f64>,
42}
43
44impl VerifyResult {
45    pub fn ok(message: impl Into<String>) -> Self {
46        Self {
47            ok: true,
48            message: message.into(),
49            value: None,
50        }
51    }
52    pub fn fail(message: impl Into<String>) -> Self {
53        Self {
54            ok: false,
55            message: message.into(),
56            value: None,
57        }
58    }
59}
60
61/// A witness to verify. Tagged by `kind` on the wire, so a witness file
62/// is `{"kind": "sidon", "n": 8, "points": [[...], ...], ...}`.
63///
64/// `claimed_size` (where present) lets a record assert "this construction
65/// has N elements" — `verify_witness` confirms the verifier passes *and*
66/// the construction has exactly that size, so a record can't claim a
67/// bigger set than the witness it ships.
68#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
69#[serde(tag = "kind", rename_all = "snake_case")]
70pub enum Witness {
71    /// A Sidon set in `{0,1}^n` under componentwise integer addition:
72    /// all pairwise sums distinct.
73    Sidon {
74        n: usize,
75        points: Vec<Vec<i64>>,
76        #[serde(default, skip_serializing_if = "Option::is_none")]
77        claimed_size: Option<usize>,
78    },
79    /// A Golomb ruler: integer marks with all pairwise differences
80    /// distinct.
81    Golomb { marks: Vec<i64> },
82    /// A cap set in `F_3^n`: no three distinct points collinear.
83    Cap {
84        n: usize,
85        points: Vec<Vec<i64>>,
86        #[serde(default, skip_serializing_if = "Option::is_none")]
87        claimed_size: Option<usize>,
88    },
89    /// A `B_h` set in `{0,1}^n`: all `h`-fold sums distinct (`h = 2` is
90    /// Sidon).
91    Bh {
92        n: usize,
93        h: usize,
94        points: Vec<Vec<i64>>,
95        #[serde(default, skip_serializing_if = "Option::is_none")]
96        claimed_size: Option<usize>,
97    },
98    /// A covering design `C(v, k, t)`: every `t`-subset of `[0, v)` lies
99    /// in at least one `k`-block.
100    Covering {
101        v: usize,
102        k: usize,
103        t: usize,
104        blocks: Vec<Vec<usize>>,
105    },
106    /// A constant-weight binary code `A(n, d, w)`: codewords of weight
107    /// exactly `w`, pairwise Hamming distance `>= d`.
108    ConstantWeight {
109        n: usize,
110        d: usize,
111        w: usize,
112        words: Vec<Vec<i64>>,
113        #[serde(default, skip_serializing_if = "Option::is_none")]
114        claimed_size: Option<usize>,
115    },
116    /// A Costas array: a permutation whose displacement vectors are all
117    /// distinct.
118    Costas { perm: Vec<i64> },
119    /// A Sidon set in `GF(2)^n` (OEIS A394031): `elements` are integer
120    /// bitmasks; the set is Sidon iff all pairwise XORs are distinct (no
121    /// four distinct elements XOR to zero). Pure integer arithmetic.
122    Gf2Sidon {
123        elements: Vec<u64>,
124        #[serde(default, skip_serializing_if = "Option::is_none")]
125        claimed_size: Option<usize>,
126    },
127    /// A union-free family (OEIS A347025): nonempty subsets of `{1..n}` such
128    /// that no member equals the union of a sub-collection of the others.
129    /// `sets` lists the members (1-based elements). The witness certifies the
130    /// LOWER bound a(n) >= |sets|; optimality (no larger family) is a separate
131    /// exhaustive search, not a witness-checkable property.
132    UnionFree {
133        n: usize,
134        sets: Vec<Vec<u32>>,
135        #[serde(default, skip_serializing_if = "Option::is_none")]
136        claimed_size: Option<usize>,
137    },
138    /// A non-attacking rook placement (OEIS A321531): `perm` is 1-based columns
139    /// (rook i sits in row i, column `perm[i]`). The verifier counts distinct
140    /// direction classes `sorted(|Δcol|,|Δrow|)/gcd` over all rook pairs. The
141    /// witness certifies the LOWER bound a(n) >= count; optimality is a
142    /// separate exhaustive search, not a witness-checkable property.
143    RookDirections {
144        n: usize,
145        perm: Vec<i64>,
146        #[serde(default, skip_serializing_if = "Option::is_none")]
147        claimed_directions: Option<usize>,
148    },
149    /// A linear `[n, k, d]_q` code given by a `k x n` generator matrix
150    /// over a prime field `GF(q)`.
151    LinearCode {
152        q: u64,
153        claimed_d: usize,
154        generator: Vec<Vec<i64>>,
155    },
156    /// An Erdős #1056 cut-equality certificate: a prime `p` and strictly
157    /// increasing cuts `c_0 < ... < c_k` such that every consecutive
158    /// interval `(c_{i-1}, c_i]` has integer product `== 1 (mod p)`.
159    IntervalProduct { p: u64, cuts: Vec<u64> },
160    /// A balanced r-coloring of K_n (Erdős #617 shape): every
161    /// (r+1)-vertex subset must see all r colors among its internal
162    /// edges. `edge_colors` keys are "i,j" with i<j, 0-indexed; colors
163    /// are 1..=r. For K_26 r=5 this is C(26,6)=230,230 subset checks —
164    /// instant.
165    BalancedColoring {
166        n: usize,
167        r: usize,
168        edge_colors: std::collections::BTreeMap<String, u32>,
169    },
170    /// An Erdős #203 partial CRT covering certificate: a modulus `m`
171    /// (decimal string, coprime to 6) and prime rows, each pinning the
172    /// multiplicative orders of 2 and 3 mod `p` and an affine line
173    /// `(alpha, beta, gamma, h)` such that `p | 2^k 3^l m + 1` iff
174    /// `alpha*k + beta*l == gamma (mod h)`, checked exhaustively over
175    /// `(k, l) in [0, h)^2`.
176    CrtPartialCover { m: String, rows: Vec<CrtCoverRow> },
177    /// An Erdős #684 effective lower-bound certificate: for each entry
178    /// `(k, m)`, `m = prod_{p<=k} p^(floor(log_p k)+1)` is recomputed and
179    /// adding `j + (m-1-j)` in base `p` produces zero Kummer carries for
180    /// all `2 <= j <= k`, `p <= j` — hence `f(m-1) > k`.
181    KummerNoCarry { entries: Vec<KummerEntry> },
182    /// An Erdős #700 value certificate: for each `(n, f)`,
183    /// `f = min_{1<k<=n/2} gcd(n, C(n,k))`, recomputed via Kummer
184    /// (`gcd(n, C(n,k)) = prod_{p|n} p^min(v_p(n), carries_p(k, n-k))`)
185    /// so no big integers ever materialize.
186    MinBinomGcd { cases: Vec<MinGcdCase> },
187    /// An Erdős #1093 (ELS93) deficiency certificate: for each entry,
188    /// `C(N,k)` is Kummer-defined (no prime `p <= k` divides it) and the
189    /// deficiency `delta(N,k) = #{1<=i<=k : (N-k+i) | i*C(k,i)}` equals
190    /// the claimed value (and slot positions, when given). Divisibility
191    /// is decided by smooth factorization + Legendre — `i*C(k,i)` is
192    /// never materialized.
193    BinomDeficiency { entries: Vec<DeficiencyEntry> },
194    /// An Erdős #1094 exception-enumeration certificate: every
195    /// counterexample with `N >= 2k`, `k <= k_max` arises as
196    /// `N = x + k - r` with `x | gcd(lcm(1..k), r*C(k,r))`, `k | x`.
197    /// The verifier re-enumerates all candidates and confirms the found
198    /// exception set equals the claimed `(N, k)` list exactly.
199    /// Fail-closed: an unresolved candidate aborts rather than claims.
200    BinomExceptionEnum {
201        k_max: u64,
202        exceptions: Vec<(u64, u64)>,
203    },
204    /// An UNSAT certificate: a CNF formula plus an LRAT-style clausal
205    /// proof. Each proof step adds a clause justified by reverse unit
206    /// propagation (RUP) over named antecedent clauses; the proof is
207    /// accepted only if it derives the empty clause. A propositional
208    /// claim (e.g. an Erdős finite case reduced to SAT) is verified by
209    /// replaying this proof — the solver is untrusted, the certificate
210    /// is checked. RUP only: a proof whose hints carry RAT structure is
211    /// refused, never guessed.
212    UnsatCert {
213        cnf: Vec<Vec<i64>>,
214        proof: Vec<LratStep>,
215    },
216    /// A difference triangle set (HorizonMath / coding theory): `rows` of
217    /// strictly increasing non-negative integers each starting at 0, such that
218    /// every positive within-row pairwise difference is GLOBALLY distinct (no
219    /// difference repeats anywhere in the set). A `(I, J)`-DTS has `I` rows of
220    /// `J + 1` marks; the objective is to MINIMIZE the scope (the largest mark).
221    /// `claimed_scope`, when present, must equal the recomputed scope, so a
222    /// record claim ("scope < 112") cannot ship a witness of a different scope.
223    DiffTriangle {
224        rows: Vec<Vec<i64>>,
225        #[serde(default, skip_serializing_if = "Option::is_none")]
226        claimed_scope: Option<usize>,
227    },
228    /// An Erdős #242 (Erdős–Straus, distinct variant) certificate: for every
229    /// `n` in `[3, n_max]`, distinct integers `1 <= x < y < z` with
230    /// `4/n = 1/x + 1/y + 1/z`. The verifier confirms the table is COMPLETE
231    /// over `[3, n_max]` (no gaps) and every case is exact (`4 x y z = n (yz +
232    /// xz + xy)`) with `x < y < z`. This certifies the conjecture for all
233    /// `3 <= n <= n_max` — a FINITE confirmation, not the uniform proof (which
234    /// is the open problem). Pure integer arithmetic; `cases` may be in any
235    /// order (the verifier sorts/checks coverage).
236    UnitFractionDecomp {
237        n_max: u64,
238        cases: Vec<UnitFractionCase>,
239    },
240    /// An Erdős #475 (Graham distinct-partial-sums) certificate for a fixed
241    /// prime `p`: for EVERY nonempty `A ⊆ F_p\{0}`, an ordering of `A` whose
242    /// partial sums are all distinct mod `p`. `orderings` lists one sequence per
243    /// subset; the verifier confirms `p` is prime, every ordering is a valid
244    /// rearrangement of a nonempty subset of `{1..p-1}` with distinct partial
245    /// sums mod `p`, and COVERAGE is complete (all `2^(p-1) - 1` nonempty
246    /// subsets appear exactly once). Certifies #475 for this `p` — a finite
247    /// confirmation (the question over all primes is the open problem). Pure
248    /// integer arithmetic.
249    DistinctPartialSums { p: u64, orderings: Vec<Vec<u64>> },
250    /// An Erdős #364 certificate: there are no three CONSECUTIVE powerful
251    /// integers `n, n+1, n+2` in `[1, n_max]` (a number is powerful iff every
252    /// prime in its factorisation appears to exponent `>= 2`). The verifier
253    /// re-scans `[2, n_max]` from scratch via a smallest-prime-factor sieve and
254    /// confirms no such triple exists. A finite confirmation (the question over
255    /// all integers is the open problem). `pairs_seen` is an optional sanity
256    /// echo of how many consecutive powerful PAIRS were found (e.g. (8,9)); it
257    /// does not gate the verdict.
258    PowerfulTriplesNone {
259        n_max: u64,
260        #[serde(default, skip_serializing_if = "Option::is_none")]
261        pairs_claimed: Option<u64>,
262    },
263    /// An Erdős #366 certificate: the complete set, over `[1, n_max]`, of `n`
264    /// that are 2-full (powerful: every prime exponent `>= 2`) with `n+1`
265    /// 3-full (every prime exponent `>= 3`). The verifier re-scans `[1, n_max]`
266    /// via an SPF sieve and confirms `examples` is EXACTLY the set found. An
267    /// empty `examples` is a finite confirmation that no such `n` exists in the
268    /// range (the question over all integers is open); a nonempty `examples`
269    /// exhibits genuine witnesses.
270    TwoFullThreeFull { n_max: u64, examples: Vec<u64> },
271    /// An Erdős #398 (Brocard / Brocard–Ramanujan) finite-confirmation
272    /// certificate: over `[n_min, n_max]`, `n! + 1` is a perfect square for
273    /// exactly the known `n ∈ {4,5,7}` and for no other `n`. Each non-exception
274    /// `n` carries a witnessing prime `p > n` such that `n! + 1` is a quadratic
275    /// non-residue mod `p` (recomputed from scratch with pure modular integer
276    /// arithmetic — no bignum, `n!` is never materialised). A finite confirmation
277    /// (the conjecture over all `n` is the open problem).
278    BrocardNoSquare {
279        n_min: u64,
280        n_max: u64,
281        cases: Vec<BrocardCase>,
282    },
283    /// An Erdős #306 certificate: each listed reduced `a/b` (with `b`
284    /// squarefree) is exhibited as an Egyptian expansion whose denominators are
285    /// all products of two distinct primes (squarefree semiprimes), strictly
286    /// increasing. The verifier re-checks every expansion with exact integer
287    /// arithmetic and confirms the cases are distinct rationals. A per-instance
288    /// finite confirmation (the question over all positive rationals is open);
289    /// it EXHIBITS genuine decompositions rather than claiming completeness.
290    SemiprimeEgyptian { cases: Vec<SemiprimeEgyptianCase> },
291}
292
293/// One addition step of an LRAT proof: clause `id` is the listed
294/// `literals` (empty = the empty clause = the proof goal), justified by
295/// reverse unit propagation over the antecedent clause `hints` in order.
296#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
297pub struct LratStep {
298    pub id: u64,
299    pub literals: Vec<i64>,
300    pub hints: Vec<u64>,
301    /// RAT justification, used only when the direct RUP check fails:
302    /// for EVERY db clause containing the negated pivot (the step's
303    /// FIRST literal), a `(clause_id, resolvent_hints)` pair whose
304    /// resolvent must itself be RUP. Tautological resolvents are
305    /// vacuously fine. Deletion lines remain unsupported.
306    #[serde(default, skip_serializing_if = "Vec::is_empty")]
307    pub rat_hints: Vec<(u64, Vec<u64>)>,
308}
309
310/// One prime row of an Erdős #203 partial-cover certificate.
311#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
312pub struct CrtCoverRow {
313    pub p: u64,
314    pub ord2: u64,
315    pub ord3: u64,
316    pub h: u64,
317    pub t_p: u64,
318    pub m_mod_p: u64,
319    /// `(alpha, beta, gamma, modulus)` with `modulus == h`.
320    pub line: [u64; 4],
321}
322
323/// One `(k, m)` entry of an Erdős #684 certificate.
324#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
325pub struct KummerEntry {
326    pub k: u64,
327    pub m: u64,
328}
329
330/// One `(n, f)` case of an Erdős #700 certificate.
331#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
332pub struct MinGcdCase {
333    pub n: u64,
334    pub f: u64,
335}
336
337/// One `(n, x, y, z)` case of an Erdős #242 (Erdős–Straus) certificate:
338/// `4/n = 1/x + 1/y + 1/z` with `1 <= x < y < z`.
339#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
340pub struct UnitFractionCase {
341    pub n: u64,
342    pub x: u64,
343    pub y: u64,
344    pub z: u64,
345}
346
347/// One `(n, p)` case of an Erdős #398 (Brocard) finite-confirmation certificate.
348/// For `n ∉ {4,5,7}`, `p` is a prime `> n` that WITNESSES that `n! + 1` is not a
349/// perfect square: the verifier recomputes `r = (n! + 1) mod p` and confirms `r`
350/// is a quadratic NON-residue mod `p` (Euler's criterion), which forces `n! + 1`
351/// to be a non-square (a perfect square is a residue, or `0`, mod every prime).
352/// For the three known solutions `n ∈ {4,5,7}`, `p` is ignored and the verifier
353/// confirms `n! + 1` IS the recorded perfect square (`25, 121, 5041`).
354#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
355pub struct BrocardCase {
356    pub n: u64,
357    #[serde(default)]
358    pub p: u64,
359}
360
361/// One `(a, b, denominators)` case of an Erdős #306 certificate: an Egyptian
362/// expansion `a/b = 1/n_1 + ... + 1/n_k` in which every `n_i` is a product of two
363/// DISTINCT primes (a squarefree semiprime), with `b` squarefree and the `n_i`
364/// strictly increasing. Verified with exact integer arithmetic.
365#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
366pub struct SemiprimeEgyptianCase {
367    pub a: u64,
368    pub b: u64,
369    pub denominators: Vec<u64>,
370}
371
372/// One `(k, N, delta, slots)` entry of an Erdős #1093 deficiency
373/// certificate. `n` is a decimal string (up to 38 digits / u128);
374/// `slots` is optional — when absent only the count is checked.
375#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
376pub struct DeficiencyEntry {
377    pub k: u64,
378    pub n: String,
379    pub delta: u64,
380    #[serde(default, skip_serializing_if = "Option::is_none")]
381    pub slots: Option<Vec<u64>>,
382}
383
384impl Witness {
385    /// The verifier name (matches the `kind` tag).
386    pub fn kind(&self) -> &'static str {
387        match self {
388            Witness::Sidon { .. } => "sidon",
389            Witness::Golomb { .. } => "golomb",
390            Witness::Cap { .. } => "cap",
391            Witness::Bh { .. } => "bh",
392            Witness::Covering { .. } => "covering",
393            Witness::ConstantWeight { .. } => "constant_weight",
394            Witness::Costas { .. } => "costas",
395            Witness::Gf2Sidon { .. } => "gf2_sidon",
396            Witness::UnionFree { .. } => "union_free",
397            Witness::RookDirections { .. } => "rook_directions",
398            Witness::LinearCode { .. } => "linear_code",
399            Witness::IntervalProduct { .. } => "interval_product",
400            Witness::BalancedColoring { .. } => "balanced_coloring",
401            Witness::CrtPartialCover { .. } => "crt_partial_cover",
402            Witness::KummerNoCarry { .. } => "kummer_no_carry",
403            Witness::MinBinomGcd { .. } => "min_binom_gcd",
404            Witness::BinomDeficiency { .. } => "binom_deficiency",
405            Witness::BinomExceptionEnum { .. } => "binom_exception_enum",
406            Witness::UnsatCert { .. } => "unsat_cert",
407            Witness::DiffTriangle { .. } => "diff_triangle",
408            Witness::UnitFractionDecomp { .. } => "unit_fraction_decomp",
409            Witness::DistinctPartialSums { .. } => "distinct_partial_sums",
410            Witness::PowerfulTriplesNone { .. } => "powerful_triples_none",
411            Witness::TwoFullThreeFull { .. } => "two_full_three_full",
412            Witness::BrocardNoSquare { .. } => "brocard_no_square",
413            Witness::SemiprimeEgyptian { .. } => "semiprime_egyptian",
414        }
415    }
416}
417
418/// Verify a difference triangle set: `rows` of strictly increasing
419/// non-negative integers, each starting at 0, with every positive within-row
420/// pairwise difference GLOBALLY distinct (no difference repeats across the
421/// whole set). Reports the scope (the largest mark). `claimed_scope`, when
422/// present, must equal the recomputed scope.
423pub fn verify_diff_triangle(rows: &[Vec<i64>], claimed_scope: Option<usize>) -> VerifyResult {
424    if rows.is_empty() {
425        return VerifyResult::fail("empty difference triangle set");
426    }
427    let mut diffs: HashSet<i64> = HashSet::new();
428    let mut diff_count = 0usize;
429    let mut scope: i64 = 0;
430    for (r, row) in rows.iter().enumerate() {
431        if row.len() < 2 {
432            return VerifyResult::fail(format!("row {r} has fewer than 2 marks"));
433        }
434        if row[0] != 0 {
435            return VerifyResult::fail(format!("row {r} does not start at 0"));
436        }
437        // strictly increasing, non-negative
438        for w in row.windows(2) {
439            if w[1] <= w[0] {
440                return VerifyResult::fail(format!("row {r} is not strictly increasing"));
441            }
442        }
443        scope = scope.max(*row.last().unwrap());
444        // every within-row positive difference must be globally distinct
445        for i in 0..row.len() {
446            for j in (i + 1)..row.len() {
447                let d = row[j] - row[i];
448                if !diffs.insert(d) {
449                    return VerifyResult::fail(format!(
450                        "difference {d} repeats (row {r}) — not a difference triangle set"
451                    ));
452                }
453                diff_count += 1;
454            }
455        }
456    }
457    let scope_usize = scope as usize;
458    if let Some(c) = claimed_scope
459        && c != scope_usize
460    {
461        return VerifyResult::fail(format!(
462            "verifier passed but scope {scope_usize} != claimed_scope {c}"
463        ));
464    }
465    VerifyResult::ok(format!(
466        "difference triangle set: {} rows, scope {scope_usize}, all {diff_count} within-row differences globally distinct",
467        rows.len()
468    ))
469}
470
471/// Verify a witness against its exact verifier, plus the optional
472/// `claimed_size` cross-check.
473/// Machine-checked novelty: does `new` strictly dominate `prior` for
474/// kinds with a natural order? Conservative: kinds without an obvious
475/// dominance order return Err (the caller reports "not comparable") —
476/// never a silent pass. This is the anti-AI-novelty-judge: dominance is
477/// arithmetic, not opinion.
478pub fn dominates(new: &Witness, prior: &Witness) -> Result<bool, String> {
479    use Witness::*;
480    match (new, prior) {
481        (
482            Sidon {
483                n: n1, points: p1, ..
484            },
485            Sidon {
486                n: n2, points: p2, ..
487            },
488        ) => {
489            if n1 != n2 {
490                return Err(format!("different n ({n1} vs {n2}); not comparable"));
491            }
492            Ok(p1.len() > p2.len())
493        }
494        (Golomb { marks: m1, .. }, Golomb { marks: m2, .. }) => Ok(m1.len() > m2.len()),
495        (BalancedColoring { n: n1, r: r1, .. }, BalancedColoring { n: n2, r: r2, .. }) => {
496            if r1 != r2 {
497                return Err(format!("different r ({r1} vs {r2}); not comparable"));
498            }
499            Ok(n1 > n2)
500        }
501        (IntervalProduct { p: p1, cuts: c1 }, IntervalProduct { p: p2, cuts: c2 }) => {
502            if p1 == p2 {
503                Ok(c1.len() > c2.len())
504            } else {
505                // a longer chain at ANY prime is a new k-record
506                Ok(c1.len() > c2.len())
507            }
508        }
509        _ => Err(format!(
510            "no dominance order defined between {} and {}",
511            new.kind(),
512            prior.kind()
513        )),
514    }
515}
516
517pub fn verify_witness(witness: &Witness) -> VerifyResult {
518    match witness {
519        Witness::Sidon {
520            n,
521            points,
522            claimed_size,
523        } => with_size(verify_sidon(points, *n), points.len(), *claimed_size),
524        Witness::Golomb { marks } => verify_golomb(marks),
525        Witness::Cap {
526            n,
527            points,
528            claimed_size,
529        } => with_size(verify_cap(points, *n), points.len(), *claimed_size),
530        Witness::Bh {
531            n,
532            h,
533            points,
534            claimed_size,
535        } => with_size(verify_bh(points, *n, *h), points.len(), *claimed_size),
536        Witness::Covering { v, k, t, blocks } => verify_covering(blocks, *v, *k, *t),
537        Witness::IntervalProduct { p, cuts } => verify_interval_product(*p, cuts),
538        Witness::BalancedColoring { n, r, edge_colors } => {
539            verify_balanced_coloring(*n, *r, edge_colors)
540        }
541        Witness::CrtPartialCover { m, rows } => verify_crt_partial_cover(m, rows),
542        Witness::KummerNoCarry { entries } => verify_kummer_no_carry(entries),
543        Witness::MinBinomGcd { cases } => verify_min_binom_gcd(cases),
544        Witness::BinomDeficiency { entries } => verify_binom_deficiency(entries),
545        Witness::BinomExceptionEnum { k_max, exceptions } => {
546            verify_binom_exception_enum(*k_max, exceptions)
547        }
548        Witness::UnsatCert { cnf, proof } => verify_unsat_cert(cnf, proof),
549        Witness::ConstantWeight {
550            n,
551            d,
552            w,
553            words,
554            claimed_size,
555        } => with_size(
556            verify_constant_weight(words, *n, *d, *w),
557            words.len(),
558            *claimed_size,
559        ),
560        Witness::Costas { perm } => verify_costas(perm),
561        Witness::Gf2Sidon {
562            elements,
563            claimed_size,
564        } => with_size(verify_gf2_sidon(elements), elements.len(), *claimed_size),
565        Witness::UnionFree {
566            n,
567            sets,
568            claimed_size,
569        } => with_size(verify_union_free(*n, sets), sets.len(), *claimed_size),
570        Witness::RookDirections {
571            n,
572            perm,
573            claimed_directions,
574        } => verify_rook_directions(*n, perm, *claimed_directions),
575        Witness::LinearCode {
576            q,
577            claimed_d,
578            generator,
579        } => verify_linear_code(generator, *q, *claimed_d),
580        Witness::DiffTriangle {
581            rows,
582            claimed_scope,
583        } => verify_diff_triangle(rows, *claimed_scope),
584        Witness::UnitFractionDecomp { n_max, cases } => verify_unit_fraction_decomp(*n_max, cases),
585        Witness::DistinctPartialSums { p, orderings } => {
586            verify_distinct_partial_sums(*p, orderings)
587        }
588        Witness::PowerfulTriplesNone {
589            n_max,
590            pairs_claimed,
591        } => verify_powerful_triples_none(*n_max, *pairs_claimed),
592        Witness::TwoFullThreeFull { n_max, examples } => {
593            verify_two_full_three_full(*n_max, examples)
594        }
595        Witness::BrocardNoSquare {
596            n_min,
597            n_max,
598            cases,
599        } => verify_brocard_no_square(*n_min, *n_max, cases),
600        Witness::SemiprimeEgyptian { cases } => verify_semiprime_egyptian(cases),
601    }
602}
603
604/// Erdős #366: verify `examples` is EXACTLY the set of `n` in `[1, n_max]` that
605/// are 2-full (powerful: every prime exponent `>= 2`) with `n+1` 3-full (every
606/// prime exponent `>= 3`). Re-scans `[1, n_max]` via an SPF sieve (the minimum
607/// prime exponent is computed exactly). An empty `examples` is a finite
608/// confirmation that no such `n` exists up to `n_max`; a nonempty `examples`
609/// exhibits genuine witnesses. Fail-closed: a claimed example that is not such
610/// an `n`, or a missing one, aborts.
611pub fn verify_two_full_three_full(n_max: u64, examples: &[u64]) -> VerifyResult {
612    if n_max < 1 {
613        return VerifyResult::fail("n_max must be >= 1");
614    }
615    if n_max > 200_000_000 {
616        return VerifyResult::fail("n_max too large for the in-gate sieve (cap 2e8)");
617    }
618    let n = (n_max + 1) as usize; // need n+1 too
619    let mut spf = vec![0u32; n + 1];
620    for i in 2..=n {
621        if spf[i] == 0 {
622            let mut j = i;
623            while j <= n {
624                if spf[j] == 0 {
625                    spf[j] = i as u32;
626                }
627                j += i;
628            }
629        }
630    }
631    // Minimum prime exponent in the factorisation of m (u64::MAX sentinel for m=1).
632    let min_exp = |mut m: usize| -> u64 {
633        if m <= 1 {
634            return u64::MAX;
635        }
636        let mut lo = u64::MAX;
637        while m > 1 {
638            let p = spf[m] as usize;
639            let mut e = 0;
640            while m.is_multiple_of(p) {
641                m /= p;
642                e += 1;
643            }
644            lo = lo.min(e);
645        }
646        lo
647    };
648    let mut found: Vec<u64> = Vec::new();
649    for m in 1..=(n_max as usize) {
650        if min_exp(m) >= 2 && min_exp(m + 1) >= 3 {
651            found.push(m as u64);
652        }
653    }
654    let mut claimed = examples.to_vec();
655    claimed.sort_unstable();
656    if claimed != found {
657        return VerifyResult::fail(format!(
658            "claimed examples {claimed:?} != the {} actually found in [1, {n_max}]: {found:?}",
659            found.len()
660        ));
661    }
662    if found.is_empty() {
663        VerifyResult::ok(format!(
664            "Erdős #366 finite confirmation: NO 2-full n with n+1 3-full in [1, {n_max}]. \
665             The question over all integers is the open problem."
666        ))
667    } else {
668        VerifyResult::ok(format!(
669            "Erdős #366: {} genuine witness(es) in [1, {n_max}] — 2-full n with n+1 3-full: {found:?}. \
670             Exhibits existence (the set is complete over the range).",
671            found.len()
672        ))
673    }
674}
675
676/// Erdős #364: verify there are NO three consecutive powerful integers in
677/// `[1, n_max]`. A smallest-prime-factor sieve over `[2, n_max]` makes the
678/// powerful test O(log n); the scan is fail-closed (any triple aborts). Finite
679/// confirmation (the question over all integers is open). `pairs_claimed`, if
680/// present, must equal the count of consecutive powerful pairs found.
681pub fn verify_powerful_triples_none(n_max: u64, pairs_claimed: Option<u64>) -> VerifyResult {
682    if n_max < 3 {
683        return VerifyResult::fail("n_max must be >= 3");
684    }
685    if n_max > 200_000_000 {
686        // Bound the sieve memory/time so the gate stays fast and safe.
687        return VerifyResult::fail("n_max too large for the in-gate sieve (cap 2e8)");
688    }
689    let n = n_max as usize;
690    // Smallest-prime-factor sieve.
691    let mut spf = vec![0u32; n + 1];
692    for i in 2..=n {
693        if spf[i] == 0 {
694            let mut j = i;
695            while j <= n {
696                if spf[j] == 0 {
697                    spf[j] = i as u32;
698                }
699                j += i;
700            }
701        }
702    }
703    // m is powerful iff every prime in its factorisation has exponent >= 2.
704    let is_powerful = |mut m: usize| -> bool {
705        if m == 1 {
706            return true;
707        }
708        while m > 1 {
709            let p = spf[m] as usize;
710            let mut e = 0;
711            while m.is_multiple_of(p) {
712                m /= p;
713                e += 1;
714            }
715            if e < 2 {
716                return false;
717            }
718        }
719        true
720    };
721    let mut pairs = 0u64;
722    let mut prev = is_powerful(1);
723    let mut prev2 = false;
724    for m in 2..=n {
725        let cur = is_powerful(m);
726        if cur && prev {
727            pairs += 1;
728        }
729        if cur && prev && prev2 {
730            return VerifyResult::fail(format!(
731                "found three consecutive powerful integers ending at {m} (#364 would be FALSIFIED)"
732            ));
733        }
734        prev2 = prev;
735        prev = cur;
736    }
737    if let Some(claimed) = pairs_claimed
738        && claimed != pairs
739    {
740        return VerifyResult::fail(format!(
741            "pairs_claimed {claimed} != {pairs} consecutive powerful pairs actually found"
742        ));
743    }
744    VerifyResult::ok(format!(
745        "Erdős #364 verified for [1, {n_max}]: no three consecutive powerful integers \
746         ({pairs} consecutive powerful pairs exist, e.g. 8,9). Finite confirmation; the \
747         question over all integers is the open problem."
748    ))
749}
750
751/// Erdős #475 (Graham distinct-partial-sums): for a fixed prime `p`, verify that
752/// `orderings` give, for EVERY nonempty `A ⊆ F_p\{0}`, a rearrangement of `A`
753/// whose partial sums are all distinct mod `p`. Fail-closed: a non-prime `p`, an
754/// out-of-range element, a non-distinct partial-sum sequence, or incomplete
755/// coverage of the `2^(p-1) - 1` nonempty subsets aborts. Certifies #475 for
756/// this `p` (a finite confirmation; the question over all primes is open).
757pub fn verify_distinct_partial_sums(p: u64, orderings: &[Vec<u64>]) -> VerifyResult {
758    let is_prime = |n: u64| -> bool {
759        if n < 2 {
760            return false;
761        }
762        let mut d = 2;
763        while d * d <= n {
764            if n.is_multiple_of(d) {
765                return false;
766            }
767            d += 1;
768        }
769        true
770    };
771    if !is_prime(p) {
772        return VerifyResult::fail(format!("p = {p} is not prime"));
773    }
774    // Coverage set: the sorted-subset key of each ordering must enumerate every
775    // nonempty subset of {1, .., p-1} exactly once.
776    let mut covered: HashSet<Vec<u64>> = HashSet::new();
777    for ord in orderings {
778        if ord.is_empty() {
779            return VerifyResult::fail("empty ordering (A must be nonempty)");
780        }
781        // Elements in F_p\{0} and distinct (a genuine subset rearrangement).
782        let set: HashSet<&u64> = ord.iter().collect();
783        if set.len() != ord.len() {
784            return VerifyResult::fail("ordering has a repeated element");
785        }
786        for &a in ord {
787            if a == 0 || a >= p {
788                return VerifyResult::fail(format!("element {a} not in F_{p}\\{{0}}"));
789            }
790        }
791        // Distinct partial sums mod p.
792        let mut seen: HashSet<u64> = HashSet::new();
793        let mut acc = 0u64;
794        for &a in ord {
795            acc = (acc + a) % p;
796            if !seen.insert(acc) {
797                let mut key: Vec<u64> = ord.clone();
798                key.sort_unstable();
799                return VerifyResult::fail(format!(
800                    "subset {key:?}: ordering {ord:?} has a repeated partial sum mod {p}"
801                ));
802            }
803        }
804        let mut key: Vec<u64> = ord.clone();
805        key.sort_unstable();
806        if !covered.insert(key.clone()) {
807            return VerifyResult::fail(format!("subset {key:?} covered more than once"));
808        }
809    }
810    let expected = (1u64 << (p - 1)) - 1; // 2^(p-1) - 1 nonempty subsets of {1..p-1}
811    if covered.len() as u64 != expected {
812        return VerifyResult::fail(format!(
813            "incomplete coverage: {} of {expected} nonempty subsets of F_{p}\\{{0}}",
814            covered.len()
815        ));
816    }
817    VerifyResult::ok(format!(
818        "Erdős #475 (distinct partial sums) verified for ALL nonempty A ⊆ F_{p}\\{{0}}: \
819         {expected} subsets, each orderable with distinct partial sums mod {p}. \
820         Finite confirmation; the question over all primes is the open problem."
821    ))
822}
823
824/// Erdős #242 (Erdős–Straus, distinct variant): verify that `cases` give, for
825/// EVERY `n` in `[3, n_max]`, distinct `1 <= x < y < z` with
826/// `4/n = 1/x + 1/y + 1/z`. Fail-closed: a gap in `[3, n_max]`, a non-ordered
827/// triple, or an inexact equation aborts. Certifies the conjecture for all
828/// `3 <= n <= n_max` (a FINITE confirmation; the uniform proof over all `n` is
829/// the open problem). Exact `u128` integer arithmetic, no floating point.
830pub fn verify_unit_fraction_decomp(n_max: u64, cases: &[UnitFractionCase]) -> VerifyResult {
831    if n_max < 3 {
832        return VerifyResult::fail("n_max must be >= 3 (the conjecture is stated for n > 2)");
833    }
834    // Coverage: exactly one case per n in [3, n_max], no gaps, no duplicates.
835    let mut seen: HashSet<u64> = HashSet::new();
836    for c in cases {
837        if c.n < 3 || c.n > n_max {
838            return VerifyResult::fail(format!("case n={} is outside [3, {n_max}]", c.n));
839        }
840        if !seen.insert(c.n) {
841            return VerifyResult::fail(format!("duplicate case for n={}", c.n));
842        }
843        // Distinct, ordered, positive: 1 <= x < y < z.
844        if !(1 <= c.x && c.x < c.y && c.y < c.z) {
845            return VerifyResult::fail(format!(
846                "n={}: triple ({},{},{}) is not 1 <= x < y < z",
847                c.n, c.x, c.y, c.z
848            ));
849        }
850        // Exact: 4/n = 1/x + 1/y + 1/z  <=>  4*x*y*z = n*(y*z + x*z + x*y).
851        let (n, x, y, z) = (c.n as u128, c.x as u128, c.y as u128, c.z as u128);
852        let lhs = 4u128 * x * y * z;
853        let rhs = n * (y * z + x * z + x * y);
854        if lhs != rhs {
855            return VerifyResult::fail(format!(
856                "n={}: 4/{} != 1/{}+1/{}+1/{} (exact check failed)",
857                c.n, c.n, c.x, c.y, c.z
858            ));
859        }
860    }
861    let expected = (n_max - 3 + 1) as usize;
862    if seen.len() != expected {
863        return VerifyResult::fail(format!(
864            "incomplete: covered {} of {expected} values in [3, {n_max}]",
865            seen.len()
866        ));
867    }
868    VerifyResult::ok(format!(
869        "Erdős–Straus (#242, distinct variant) verified for all 3 <= n <= {n_max}: \
870         {expected} exact decompositions 4/n = 1/x+1/y+1/z with x < y < z. \
871         Finite confirmation; the uniform proof over all n is the open problem."
872    ))
873}
874
875/// Erdős #398 (Brocard's problem, `n! + 1 = m^2`): over `[n_min, n_max]`, confirm
876/// `n! + 1` is a perfect square for exactly the known `n ∈ {4,5,7}` and for no
877/// other `n`. Each non-exception `n` carries a witnessing prime `p > n` and the
878/// verifier recomputes `r = (n! + 1) mod p` (iterated modular product — `n!` is
879/// never materialised, so no bignum) and confirms via Euler's criterion that `r`
880/// is a quadratic NON-residue mod `p`, which forces `n! + 1` to be a non-square.
881/// Fail-closed: a non-prime / too-small `p`, a residue `r`, `r = 0`, a wrong
882/// known-solution, or incomplete coverage of `[n_min, n_max]` aborts. A finite
883/// confirmation (the conjecture over all `n` is the open problem).
884pub fn verify_brocard_no_square(n_min: u64, n_max: u64, cases: &[BrocardCase]) -> VerifyResult {
885    if n_min < 1 || n_max < n_min {
886        return VerifyResult::fail("require 1 <= n_min <= n_max");
887    }
888    if n_max > 5_000_000 {
889        return VerifyResult::fail("n_max too large for the in-gate certificate (cap 5e6)");
890    }
891    let is_prime = |n: u64| -> bool {
892        if n < 2 {
893            return false;
894        }
895        if n.is_multiple_of(2) {
896            return n == 2;
897        }
898        let mut d = 3u64;
899        while d * d <= n {
900            if n.is_multiple_of(d) {
901                return false;
902            }
903            d += 2;
904        }
905        true
906    };
907    // Modular exponentiation in u128 (base, exp already reduced sensibly).
908    let mod_pow = |mut base: u128, mut exp: u128, modulus: u128| -> u128 {
909        if modulus == 1 {
910            return 0;
911        }
912        let mut result = 1u128;
913        base %= modulus;
914        while exp > 0 {
915            if exp & 1 == 1 {
916                result = result * base % modulus;
917            }
918            exp >>= 1;
919            base = base * base % modulus;
920        }
921        result
922    };
923    // The three known Brocard solutions: 4!+1=25, 5!+1=121, 7!+1=5041.
924    let known: [u64; 3] = [4, 5, 7];
925    let mut seen: HashSet<u64> = HashSet::new();
926    for c in cases {
927        if c.n < n_min || c.n > n_max {
928            return VerifyResult::fail(format!("case n={} outside [{n_min}, {n_max}]", c.n));
929        }
930        if !seen.insert(c.n) {
931            return VerifyResult::fail(format!("duplicate case for n={}", c.n));
932        }
933        if known.contains(&c.n) {
934            // Confirm n!+1 IS a perfect square (n <= 7, so n! fits easily).
935            let mut fact: u128 = 1;
936            for k in 1..=c.n as u128 {
937                fact *= k;
938            }
939            let val = fact + 1;
940            let root = (val as f64).sqrt() as u128;
941            let mut is_sq = false;
942            for m in root.saturating_sub(2)..=root + 2 {
943                if m * m == val {
944                    is_sq = true;
945                    break;
946                }
947            }
948            if !is_sq {
949                return VerifyResult::fail(format!(
950                    "n={}: {}!+1 = {val} is not a perfect square (expected a known solution)",
951                    c.n, c.n
952                ));
953            }
954        } else {
955            // Non-exception: a witnessing prime p > n with n!+1 a non-residue mod p.
956            let p = c.p;
957            if p <= c.n {
958                return VerifyResult::fail(format!(
959                    "n={}: witnessing prime p={p} must exceed n",
960                    c.n
961                ));
962            }
963            if !is_prime(p) {
964                return VerifyResult::fail(format!("n={}: p={p} is not prime", c.n));
965            }
966            let pm = p as u128;
967            let mut fact = 1u128;
968            for k in 1..=c.n {
969                fact = fact * (k as u128) % pm;
970            }
971            let r = (fact + 1) % pm;
972            if r == 0 {
973                return VerifyResult::fail(format!(
974                    "n={}: n!+1 ≡ 0 (mod {p}); that does not prove a non-square",
975                    c.n
976                ));
977            }
978            // Euler's criterion: r is a non-residue iff r^((p-1)/2) ≡ -1 (mod p).
979            let legendre = mod_pow(r, (pm - 1) / 2, pm);
980            if legendre != pm - 1 {
981                return VerifyResult::fail(format!(
982                    "n={}: r={r} is a quadratic residue mod {p} \
983                     (r^((p-1)/2) mod p = {legendre}, need {}); n!+1 not shown non-square",
984                    c.n,
985                    pm - 1
986                ));
987            }
988        }
989    }
990    let expected = (n_max - n_min + 1) as usize;
991    if seen.len() != expected {
992        return VerifyResult::fail(format!(
993            "incomplete: covered {} of {expected} values in [{n_min}, {n_max}]",
994            seen.len()
995        ));
996    }
997    let exceptions: Vec<u64> = known
998        .iter()
999        .copied()
1000        .filter(|&n| n >= n_min && n <= n_max)
1001        .collect();
1002    VerifyResult::ok(format!(
1003        "Erdős #398 (Brocard) verified for all {n_min} <= n <= {n_max}: n!+1 is a perfect \
1004         square exactly for n in {exceptions:?}, and a non-square (quadratic-non-residue \
1005         certificate mod a witnessing prime) for every other n. Finite confirmation; the \
1006         conjecture over all n is the open problem."
1007    ))
1008}
1009
1010/// Erdős #306: verify each listed reduced `a/b` (with `b` squarefree) is exhibited
1011/// as an Egyptian expansion `a/b = sum 1/n_i` whose denominators `n_i` are all
1012/// products of two DISTINCT primes (squarefree semiprimes), strictly increasing.
1013/// Exact integer arithmetic (reduced-fraction accumulation, no floats). Fail-closed:
1014/// a non-squarefree `b`, a denominator that is not a distinct-prime product, a
1015/// non-increasing list, a mismatched sum, or a duplicated rational aborts. A
1016/// per-instance finite confirmation (the question over all positive rationals is open).
1017pub fn verify_semiprime_egyptian(cases: &[SemiprimeEgyptianCase]) -> VerifyResult {
1018    if cases.is_empty() {
1019        return VerifyResult::fail("no cases supplied");
1020    }
1021    let gcd = |mut a: u64, mut b: u64| -> u64 {
1022        while b != 0 {
1023            let t = a % b;
1024            a = b;
1025            b = t;
1026        }
1027        a
1028    };
1029    let gcd128 = |mut a: u128, mut b: u128| -> u128 {
1030        while b != 0 {
1031            let t = a % b;
1032            a = b;
1033            b = t;
1034        }
1035        a
1036    };
1037    // n is a squarefree semiprime iff it factors as p*q with p<q both prime
1038    // (exactly two distinct prime factors, each to exponent 1).
1039    let is_squarefree_semiprime = |n: u64| -> bool {
1040        if n < 6 {
1041            return false;
1042        }
1043        let mut m = n;
1044        let mut factors = 0u32;
1045        let mut d = 2u64;
1046        while d * d <= m {
1047            if m.is_multiple_of(d) {
1048                let mut e = 0u32;
1049                while m.is_multiple_of(d) {
1050                    m /= d;
1051                    e += 1;
1052                }
1053                if e != 1 {
1054                    return false; // a repeated prime => not squarefree
1055                }
1056                factors += 1;
1057            }
1058            d += 1;
1059        }
1060        if m > 1 {
1061            factors += 1;
1062        }
1063        factors == 2
1064    };
1065    let is_squarefree = |mut n: u64| -> bool {
1066        let mut d = 2u64;
1067        while d * d <= n {
1068            if n.is_multiple_of(d) {
1069                n /= d;
1070                if n.is_multiple_of(d) {
1071                    return false;
1072                }
1073            } else {
1074                d += 1;
1075            }
1076        }
1077        true
1078    };
1079    let mut seen: HashSet<(u64, u64)> = HashSet::new();
1080    for c in cases {
1081        if c.a == 0 || c.b == 0 {
1082            return VerifyResult::fail("a and b must be positive");
1083        }
1084        let g = gcd(c.a, c.b);
1085        let (ar, br) = (c.a / g, c.b / g);
1086        if !is_squarefree(br) {
1087            return VerifyResult::fail(format!(
1088                "{}/{}: reduced denominator {br} is not squarefree",
1089                c.a, c.b
1090            ));
1091        }
1092        if !seen.insert((ar, br)) {
1093            return VerifyResult::fail(format!("duplicate rational {ar}/{br}"));
1094        }
1095        let d = &c.denominators;
1096        if d.is_empty() {
1097            return VerifyResult::fail(format!("{ar}/{br}: empty denominator list"));
1098        }
1099        for w in d.windows(2) {
1100            if w[0] >= w[1] {
1101                return VerifyResult::fail(format!(
1102                    "{ar}/{br}: denominators must be strictly increasing"
1103                ));
1104            }
1105        }
1106        for &ni in d {
1107            if !is_squarefree_semiprime(ni) {
1108                return VerifyResult::fail(format!(
1109                    "{ar}/{br}: denominator {ni} is not a product of two distinct primes"
1110                ));
1111            }
1112        }
1113        // Exact sum 1/n_i via reduced-fraction accumulation (u128, gcd each step).
1114        let mut sn: u128 = 0;
1115        let mut sd: u128 = 1;
1116        for &ni in d {
1117            let ni = ni as u128;
1118            let nn = sn.checked_mul(ni).and_then(|v| v.checked_add(sd));
1119            let nd = sd.checked_mul(ni);
1120            match (nn, nd) {
1121                (Some(nn), Some(nd)) => {
1122                    let g = gcd128(nn, nd).max(1);
1123                    sn = nn / g;
1124                    sd = nd / g;
1125                }
1126                _ => {
1127                    return VerifyResult::fail(format!(
1128                        "{ar}/{br}: denominator product overflow (expansion too long/large)"
1129                    ));
1130                }
1131            }
1132        }
1133        // Compare sn/sd to ar/br exactly via cross-multiplication (checked).
1134        let lhs = sn.checked_mul(br as u128);
1135        let rhs = (ar as u128).checked_mul(sd);
1136        match (lhs, rhs) {
1137            (Some(l), Some(r)) if l == r => {}
1138            (Some(_), Some(_)) => {
1139                return VerifyResult::fail(format!(
1140                    "{ar}/{br}: sum of 1/n_i = {sn}/{sd} != {ar}/{br}"
1141                ));
1142            }
1143            _ => {
1144                return VerifyResult::fail(format!("{ar}/{br}: overflow comparing the exact sum"));
1145            }
1146        }
1147    }
1148    VerifyResult::ok(format!(
1149        "Erdős #306 verified: {} reduced a/b (b squarefree) each exhibited as an Egyptian \
1150         expansion into distinct squarefree-semiprime unit fractions. Per-instance finite \
1151         confirmation; the question over all positive rationals is the open problem.",
1152        cases.len()
1153    ))
1154}
1155
1156/// A claim parsed from a finding's free-text assertion into the structured,
1157/// frozen-verifiable shape needed to BIND it to a witness. Deliberately
1158/// conservative: `parse_claim` returns `None` for anything it cannot read
1159/// unambiguously, so an unrecognized assertion is never faithful (fail-closed).
1160#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
1161pub struct ParsedClaim {
1162    /// The witness kind keyword found in the assertion (e.g. "sidon").
1163    pub kind: String,
1164    /// The ambient dimension / order `n`, reconciled from the OEIS order
1165    /// `a(N)` and/or an ambient literal (`{0,1}^N` / `GF(2)^N` / `F_3^N`).
1166    /// `None` only when the assertion states neither.
1167    pub ambient_n: Option<usize>,
1168    /// The claimed size / order bound `k`.
1169    pub bound: usize,
1170    /// `true` when the claim is an equality (`= k` / `exactly k`), `false`
1171    /// for a lower bound (`>= k` / `at least k`). Only lower bounds and
1172    /// matched equalities are admissible.
1173    pub exact: bool,
1174    /// The B_h order `h` (from `B_<h>` / `<h>-fold`), when stated. Bound to the
1175    /// witness `h` for `bh` claims; required for B_h floor-admission.
1176    #[serde(default, skip_serializing_if = "Option::is_none")]
1177    pub h: Option<usize>,
1178    /// The constant-weight code distance `d` and weight `w` (from the
1179    /// `A(n,d,w)` signature), when stated. Both bound to the witness for
1180    /// `constant_weight` floor-admission.
1181    #[serde(default, skip_serializing_if = "Option::is_none")]
1182    pub d: Option<usize>,
1183    #[serde(default, skip_serializing_if = "Option::is_none")]
1184    pub w: Option<usize>,
1185}
1186
1187/// The frozen faithfulness verdict: does `witness` ESTABLISH the claim in
1188/// `assertion_text`? This is the load-bearing, un-forgeable check the
1189/// exact-lane auto-admission rests on. `verify_witness` only confirms a
1190/// witness is INTERNALLY valid (a genuine Sidon set of size `points.len()`);
1191/// it never reads the assertion, so an INFLATED assertion ("a(20) >= 2500")
1192/// over a valid-but-weaker witness (a real Sidon set of 1989 points) would
1193/// pass `verify_witness`. `claim_witness_faithful` closes that: it re-derives
1194/// faithfulness from frozen inputs (the parsed assertion + the witness
1195/// structure), never from the drafter-set `match_to_claim.matches` flag an
1196/// agent can author. `faithful` is true only when the witness both verifies
1197/// AND its parameters meet/exceed the parsed claim.
1198#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
1199pub struct Faithfulness {
1200    pub faithful: bool,
1201    pub reasons: Vec<String>,
1202    #[serde(default, skip_serializing_if = "Option::is_none")]
1203    pub parsed: Option<ParsedClaim>,
1204}
1205
1206/// Leading `usize` from a string slice after skipping ASCII whitespace.
1207fn leading_usize(s: &str) -> Option<usize> {
1208    let s = s.trim_start();
1209    let digits: String = s.chars().take_while(|c| c.is_ascii_digit()).collect();
1210    if digits.is_empty() {
1211        None
1212    } else {
1213        digits.parse().ok()
1214    }
1215}
1216
1217/// The `usize` immediately following the EARLIEST occurrence of any `needle`
1218/// (the headline bound, so a trailing "(was N)" aside cannot override it).
1219fn usize_after_any(hay: &str, needles: &[&str]) -> Option<usize> {
1220    let mut best: Option<(usize, usize)> = None; // (value, position)
1221    for needle in needles {
1222        if let Some(idx) = hay.find(needle)
1223            && let Some(v) = leading_usize(&hay[idx + needle.len()..])
1224            && best.map(|(_, p)| idx < p).unwrap_or(true)
1225        {
1226            best = Some((v, idx));
1227        }
1228    }
1229    best.map(|(v, _)| v)
1230}
1231
1232/// The `usize` inside the first `a(N)` group (the OEIS order/index form),
1233/// e.g. `a(20)` -> `20`. The match requires a literal `a(` so a sequence id
1234/// like `a309370` (no paren) is not mistaken for an order.
1235fn order_in_a_paren(text: &str) -> Option<usize> {
1236    text.find("a(").and_then(|i| leading_usize(&text[i + 2..]))
1237}
1238
1239/// The `usize` of an EQUALITY / optimality marker: `exactly N`, or a standalone
1240/// `= N` whose `=` is NOT part of a `>=` / `<=` / `!=` / `==` operator. A
1241/// witness establishes a lower bound, never an equality, so any such marker is
1242/// a fail-closed signal (and a `= N` headline beside an `at least k` clause is
1243/// the dual-bound inflation the exact lane must reject).
1244fn equality_bound(text: &str) -> Option<usize> {
1245    if let Some(v) = usize_after_any(text, &["exactly "]) {
1246        return Some(v);
1247    }
1248    let mut from = 0;
1249    while let Some(rel) = text[from..].find('=') {
1250        let idx = from + rel;
1251        let prev = text[..idx].chars().last();
1252        let compound = matches!(
1253            prev,
1254            Some('>') | Some('<') | Some('!') | Some('=') | Some('\u{2265}') | Some('\u{2264}')
1255        );
1256        if !compound && let Some(v) = leading_usize(&text[idx + 1..]) {
1257            return Some(v);
1258        }
1259        from = idx + 1;
1260    }
1261    None
1262}
1263
1264/// The B_h order `h` from the standard subscript form `b_<h>` and/or the
1265/// `<h>-fold` form. Disagreeing signals -> `None` (fail closed via the
1266/// mandatory bind). `b_h` with a literal `h` (no digit) yields `None`.
1267fn bh_order(text: &str) -> Option<usize> {
1268    let subscript = text.find("b_").and_then(|i| leading_usize(&text[i + 2..]));
1269    let fold = text.find("-fold").and_then(|i| {
1270        let pre: String = text[..i]
1271            .chars()
1272            .rev()
1273            .take_while(|c| c.is_ascii_digit())
1274            .collect();
1275        pre.chars().rev().collect::<String>().parse().ok()
1276    });
1277    match (subscript, fold) {
1278        (Some(a), Some(b)) if a != b => None,
1279        (Some(a), _) => Some(a),
1280        (None, Some(b)) => Some(b),
1281        (None, None) => None,
1282    }
1283}
1284
1285/// The constant-weight `A(n, d, w)` triple from the first `a(...)` group that
1286/// holds exactly three comma-separated integers. `None` when the signature is
1287/// absent or malformed (so `(d, w)` go unbound and the claim routes to review).
1288fn cw_params(text: &str) -> Option<(usize, usize, usize)> {
1289    let i = text.find("a(")?;
1290    let rest = &text[i + 2..];
1291    let close = rest.find(')')?;
1292    let parts: Vec<&str> = rest[..close].split(',').collect();
1293    if parts.len() != 3 {
1294        return None;
1295    }
1296    Some((
1297        parts[0].trim().parse().ok()?,
1298        parts[1].trim().parse().ok()?,
1299        parts[2].trim().parse().ok()?,
1300    ))
1301}
1302
1303/// Parse a finding assertion into a [`ParsedClaim`]. Conservative and
1304/// fail-closed: recognizes only the lower-bound forms the exact lane admits,
1305/// and returns `None` on any ambiguity (no kind keyword, no parseable bound,
1306/// an equality/optimality marker, two disagreeing dimension signals, or a
1307/// lower bound co-occurring with an equality marker).
1308pub fn parse_claim(assertion_text: &str) -> Option<ParsedClaim> {
1309    let text = assertion_text.to_lowercase();
1310
1311    // Witness-kind keyword. Order matters: check the more specific ones first.
1312    let kind = if text.contains("gf(2)") && text.contains("sidon") {
1313        "gf2_sidon"
1314    } else if text.contains("sidon") {
1315        "sidon"
1316    } else if text.contains("golomb") {
1317        "golomb"
1318    } else if text.contains("cap set") || text.contains("cap-set") {
1319        "cap"
1320    } else if text.contains("b_h") || text.contains("bh set") || bh_order(&text).is_some() {
1321        "bh"
1322    } else if text.contains("constant weight") || text.contains("constant-weight") {
1323        "constant_weight"
1324    } else if text.contains("union-free") || text.contains("union free") {
1325        "union_free"
1326    } else {
1327        return None;
1328    };
1329
1330    // Dimension / order. Two independent signals: the OEIS order `a(N)` and an
1331    // ambient-space literal (`{0,1}^N`, `gf(2)^N`, `f_3^N`). Reading the `a(N)`
1332    // order (not only the literal) is what binds an OEIS "a(20)" claim to the
1333    // witness even when the prose omits a `{0,1}^20` literal. If BOTH signals
1334    // are present and DISAGREE the claim is ambiguous -> fail closed.
1335    let order = order_in_a_paren(&text);
1336    let literal = ["{0,1}^", "gf(2)^", "f_3^"].iter().find_map(|m| {
1337        text.find(m)
1338            .and_then(|i| leading_usize(&text[i + m.len()..]))
1339    });
1340    let ambient_n = match (order, literal) {
1341        (Some(a), Some(b)) if a != b => return None,
1342        (Some(a), _) => Some(a),
1343        (None, Some(b)) => Some(b),
1344        (None, None) => None,
1345    };
1346
1347    // Bound: exactly one unambiguous lower bound (`>=`, `≥`, `at least`). An
1348    // equality / optimality marker (`exactly N`, or a standalone `= N`) is not
1349    // witness-establishable, and a lower bound co-occurring with one is
1350    // ambiguous (a `= 2500` headline beside an `at least 5` clause): both fail
1351    // closed.
1352    let lower = usize_after_any(&text, &[">=", "\u{2265}", "at least "]);
1353    let equality = equality_bound(&text);
1354    let (bound, is_exact) = match (lower, equality) {
1355        (Some(l), None) => (l, false),
1356        (None, Some(e)) => (e, true),
1357        // both present, or neither: ambiguous / unparseable -> fail closed.
1358        _ => return None,
1359    };
1360
1361    // Extra hardness parameters, bound per-kind in claim_witness_faithful.
1362    let h = bh_order(&text);
1363    let (d, w) = match cw_params(&text) {
1364        Some((_, d, w)) => (Some(d), Some(w)),
1365        None => (None, None),
1366    };
1367
1368    Some(ParsedClaim {
1369        kind: kind.to_string(),
1370        ambient_n,
1371        bound,
1372        exact: is_exact,
1373        h,
1374        d,
1375        w,
1376    })
1377}
1378
1379/// Frozen check that `witness` establishes the claim in `assertion_text`.
1380/// See [`Faithfulness`] for why this is the un-forgeable core of the exact
1381/// lane. Fail-closed throughout: any parse miss, kind/dimension mismatch,
1382/// size shortfall, or internal-validity failure yields `faithful: false`.
1383pub fn claim_witness_faithful(assertion_text: &str, witness: &Witness) -> Faithfulness {
1384    verify_witness_with_claim(assertion_text, witness).1
1385}
1386
1387/// Verify the witness and bind an exact claim with one mechanical pass.
1388///
1389/// Callers that need both results should use this function instead of invoking
1390/// [`verify_witness`] and [`claim_witness_faithful`] separately. Large exact
1391/// constructions can make verification expensive; the claim check consumes
1392/// the result produced here and never reruns the verifier.
1393pub fn verify_witness_with_claim(
1394    assertion_text: &str,
1395    witness: &Witness,
1396) -> (VerifyResult, Faithfulness) {
1397    let verification = verify_witness(witness);
1398    let faithfulness =
1399        claim_witness_faithful_from_verification(assertion_text, witness, &verification);
1400    (verification, faithfulness)
1401}
1402
1403fn claim_witness_faithful_from_verification(
1404    assertion_text: &str,
1405    witness: &Witness,
1406    verification: &VerifyResult,
1407) -> Faithfulness {
1408    let mut reasons = Vec::new();
1409
1410    let Some(parsed) = parse_claim(assertion_text) else {
1411        reasons.push(
1412            "assertion does not parse to a recognized exact-lane claim (kind keyword + a single \
1413             unambiguous >=/exactly bound); routes to review"
1414                .to_string(),
1415        );
1416        return Faithfulness {
1417            faithful: false,
1418            reasons,
1419            parsed: None,
1420        };
1421    };
1422
1423    // The witness must be internally valid first (a genuine Sidon set, etc.).
1424    if !verification.ok {
1425        reasons.push(format!("witness does not verify: {}", verification.message));
1426        return Faithfulness {
1427            faithful: false,
1428            reasons,
1429            parsed: Some(parsed),
1430        };
1431    }
1432
1433    // Kind must match the witness variant.
1434    if parsed.kind != witness.kind() {
1435        reasons.push(format!(
1436            "claim kind '{}' does not match witness kind '{}'",
1437            parsed.kind,
1438            witness.kind()
1439        ));
1440        return Faithfulness {
1441            faithful: false,
1442            reasons,
1443            parsed: Some(parsed),
1444        };
1445    }
1446
1447    // A construction witness establishes a LOWER bound (a(n) >= size). An
1448    // equality / optimality claim (`=` / `exactly`) additionally asserts that
1449    // no larger object exists, which a single witness cannot prove; route it to
1450    // review rather than admit it on the witness alone.
1451    if parsed.exact {
1452        reasons.push(
1453            "equality/optimality claim (= / exactly) is not establishable by a construction \
1454             witness (which proves only a lower bound); routes to review"
1455                .to_string(),
1456        );
1457        return Faithfulness {
1458            faithful: false,
1459            reasons,
1460            parsed: Some(parsed),
1461        };
1462    }
1463
1464    // The witness's size/order must meet the claimed bound AND the claimed
1465    // dimension must bind to the witness. Every size/order-bearing kind MUST
1466    // carry a parsed dimension (the `a(N)` order or an ambient literal); a
1467    // dimensioned claim that omits it is the omit-dimension bypass (a small
1468    // witness backing an `a(20)` headline) and routes to review.
1469    let dim_n_witness = |n: usize| -> Option<String> {
1470        match parsed.ambient_n {
1471            None => Some(
1472                "dimensioned claim states no ambient dimension (a(N) / {0,1}^N / gf(2)^N); \
1473                 routes to review"
1474                    .to_string(),
1475            ),
1476            Some(c) if c != n => Some(format!(
1477                "claim ambient dimension n={c} does not match witness n={n}"
1478            )),
1479            Some(_) => None,
1480        }
1481    };
1482
1483    // The floor admits a kind only when EVERY witness-defining parameter that
1484    // changes a record's hardness is parsed from the assertion and bound to the
1485    // witness — not just the ambient dimension `n`. A third adversarial review
1486    // showed binding `n` alone is insufficient: verify_witness checks a witness
1487    // against its OWN author-set h/d/w, so an EASY witness (B_2, or A(n,2,1))
1488    // could back a HARD headline (B_3, or A(n,10,8)). B_h now binds the order
1489    // `h`, constant-weight binds `(d, w)`; both route to review when the
1490    // parameter is unstated. Golomb (a min-length problem) still has no sound
1491    // witness->lower-bound binding and routes to review.
1492    let size: usize = match witness {
1493        Witness::Sidon { n, points, .. } | Witness::Cap { n, points, .. } => {
1494            if let Some(r) = dim_n_witness(*n) {
1495                reasons.push(r);
1496                return Faithfulness {
1497                    faithful: false,
1498                    reasons,
1499                    parsed: Some(parsed),
1500                };
1501            }
1502            points.len()
1503        }
1504        Witness::UnionFree { n, sets, .. } => {
1505            if let Some(r) = dim_n_witness(*n) {
1506                reasons.push(r);
1507                return Faithfulness {
1508                    faithful: false,
1509                    reasons,
1510                    parsed: Some(parsed),
1511                };
1512            }
1513            sets.len()
1514        }
1515        Witness::Gf2Sidon { elements, .. } => {
1516            // The claimed dimension N is mandatory, and every element must live
1517            // in GF(2)^N (no set bit at index >= N). A witness in GF(2)^12 must
1518            // NOT establish an a(5) claim; the element-fit check binds it.
1519            let Some(claim_n) = parsed.ambient_n else {
1520                reasons.push(
1521                    "GF(2)-Sidon claim states no dimension N (a(N) / gf(2)^N); routes to review"
1522                        .to_string(),
1523                );
1524                return Faithfulness {
1525                    faithful: false,
1526                    reasons,
1527                    parsed: Some(parsed),
1528                };
1529            };
1530            if claim_n >= 64 || elements.iter().any(|e| (*e >> claim_n) != 0) {
1531                reasons.push(format!(
1532                    "witness has an element outside GF(2)^{claim_n}; it does not establish a(N) \
1533                     at that dimension"
1534                ));
1535                return Faithfulness {
1536                    faithful: false,
1537                    reasons,
1538                    parsed: Some(parsed),
1539                };
1540            }
1541            elements.len()
1542        }
1543        Witness::Bh { n, h, points, .. } => {
1544            // B_h binds the ambient n AND the order h (a B_3 set admits strictly
1545            // fewer points than B_2). h is mandatory and must match the witness;
1546            // an unstated or mismatched h routes to review.
1547            if let Some(r) = dim_n_witness(*n) {
1548                reasons.push(r);
1549                return Faithfulness {
1550                    faithful: false,
1551                    reasons,
1552                    parsed: Some(parsed),
1553                };
1554            }
1555            match parsed.h {
1556                Some(ch) if ch == *h => {}
1557                Some(ch) => {
1558                    reasons.push(format!(
1559                        "claim B_{ch} does not match witness B_{h} (the order h binds the record)"
1560                    ));
1561                    return Faithfulness {
1562                        faithful: false,
1563                        reasons,
1564                        parsed: Some(parsed),
1565                    };
1566                }
1567                None => {
1568                    reasons.push(
1569                        "B_h claim does not state the order h (B_<h> / <h>-fold); routes to review"
1570                            .to_string(),
1571                    );
1572                    return Faithfulness {
1573                        faithful: false,
1574                        reasons,
1575                        parsed: Some(parsed),
1576                    };
1577                }
1578            }
1579            points.len()
1580        }
1581        Witness::ConstantWeight { n, d, w, words, .. } => {
1582            // A constant-weight record A(n,d,w) binds the ambient n AND the
1583            // minimum distance d and weight w; a trivial A(n,2,1) witness must
1584            // not back a hard A(n,10,8) claim. Both d and w are mandatory (from
1585            // the `A(n,d,w)` signature) and must match the witness.
1586            if let Some(r) = dim_n_witness(*n) {
1587                reasons.push(r);
1588                return Faithfulness {
1589                    faithful: false,
1590                    reasons,
1591                    parsed: Some(parsed),
1592                };
1593            }
1594            match (parsed.d, parsed.w) {
1595                (Some(cd), Some(cw)) if cd == *d && cw == *w => {}
1596                (Some(cd), Some(cw)) => {
1597                    reasons.push(format!(
1598                        "claim A(n,{cd},{cw}) does not match witness A(n,{d},{w}) (d,w bind the record)"
1599                    ));
1600                    return Faithfulness {
1601                        faithful: false,
1602                        reasons,
1603                        parsed: Some(parsed),
1604                    };
1605                }
1606                _ => {
1607                    reasons.push(
1608                        "constant-weight claim does not state (d,w) as A(n,d,w); routes to review"
1609                            .to_string(),
1610                    );
1611                    return Faithfulness {
1612                        faithful: false,
1613                        reasons,
1614                        parsed: Some(parsed),
1615                    };
1616                }
1617            }
1618            words.len()
1619        }
1620        Witness::Golomb { .. } => {
1621            // A Golomb claim is a MIN-length problem (a(n) <= length); a ruler
1622            // witness does not establish a >= lower bound the same way, and no
1623            // sound witness->claim binding is defined here. Route to review.
1624            reasons.push(
1625                "golomb claims are not floor-admissible (no sound witness->bound binding \
1626                 defined); routes to review"
1627                    .to_string(),
1628            );
1629            return Faithfulness {
1630                faithful: false,
1631                reasons,
1632                parsed: Some(parsed),
1633            };
1634        }
1635        // Any other variant is outside the size/order-bearing exact lane.
1636        _ => {
1637            reasons.push(format!(
1638                "witness kind '{}' is not an exact-lane size/order claim",
1639                witness.kind()
1640            ));
1641            return Faithfulness {
1642                faithful: false,
1643                reasons,
1644                parsed: Some(parsed),
1645            };
1646        }
1647    };
1648
1649    if size < parsed.bound {
1650        reasons.push(format!(
1651            "witness size/order {size} does not establish the claimed >= {}",
1652            parsed.bound
1653        ));
1654        return Faithfulness {
1655            faithful: false,
1656            reasons,
1657            parsed: Some(parsed),
1658        };
1659    }
1660
1661    Faithfulness {
1662        faithful: true,
1663        reasons,
1664        parsed: Some(parsed),
1665    }
1666}
1667
1668/// The canonical, WITNESS-DERIVED verified claim for a floor-admissible witness:
1669/// exactly the lower bound the witness structurally establishes, independent of
1670/// the author's assertion prose. Surfaces should DISPLAY this as the verified
1671/// `machine_verified` claim (with the prose shown only as an unverified
1672/// description), so author prose cannot puff a true bound into a false headline.
1673/// `None` for kinds that are not floor-admissible. Mirrors the binding in
1674/// `claim_witness_faithful` (kind, n, the bound-defining parameters, size).
1675pub fn canonical_claim(witness: &Witness) -> Option<String> {
1676    match witness {
1677        Witness::Sidon { n, points, .. } => Some(format!(
1678            "Sidon set: a({n}) >= {} (a Sidon set of {} points in {{0,1}}^{n})",
1679            points.len(),
1680            points.len()
1681        )),
1682        Witness::Cap { n, points, .. } => Some(format!(
1683            "cap set: a({n}) >= {} (a cap set of {} points in F_3^{n})",
1684            points.len(),
1685            points.len()
1686        )),
1687        Witness::Gf2Sidon { elements, .. } => {
1688            // The witness lives in GF(2)^n for n = the widest element's bit
1689            // width; that is the strongest (smallest-n) true statement.
1690            let n = elements
1691                .iter()
1692                .map(|e| (64 - e.leading_zeros()) as usize)
1693                .max()
1694                .unwrap_or(0);
1695            Some(format!(
1696                "GF(2)-Sidon set: a({n}) >= {} (a Sidon set of {} elements in GF(2)^{n})",
1697                elements.len(),
1698                elements.len()
1699            ))
1700        }
1701        Witness::UnionFree { n, sets, .. } => Some(format!(
1702            "union-free family: a({n}) >= {} (a union-free family of {} subsets of {{1..{n}}})",
1703            sets.len(),
1704            sets.len()
1705        )),
1706        Witness::Bh { n, h, points, .. } => Some(format!(
1707            "B_{h} set: a({n}) >= {} (a B_{h} set of {} points in {{0,1}}^{n})",
1708            points.len(),
1709            points.len()
1710        )),
1711        Witness::ConstantWeight { n, d, w, words, .. } => Some(format!(
1712            "constant-weight code: A({n},{d},{w}) >= {} ({} codewords of length {n}, weight {w}, min distance {d})",
1713            words.len(),
1714            words.len()
1715        )),
1716        // Not floor-admissible (golomb, covering, costas, rook, linear_code, ...).
1717        _ => None,
1718    }
1719}
1720
1721/// Fold a `claimed_size` cross-check into a verifier result: the witness
1722/// must pass AND have exactly the claimed number of elements.
1723fn with_size(mut r: VerifyResult, actual: usize, claimed: Option<usize>) -> VerifyResult {
1724    if r.ok
1725        && let Some(c) = claimed
1726    {
1727        if actual != c {
1728            return VerifyResult::fail(format!(
1729                "verifier passed but construction size {actual} != claimed_size {c}"
1730            ));
1731        }
1732        r.message = format!("{} (size {actual} = claimed)", r.message);
1733    }
1734    r
1735}
1736
1737// --- combinatorial verifiers ---------------------------------------------
1738
1739fn binary_points_ok(points: &[Vec<i64>], n: usize) -> Option<VerifyResult> {
1740    let set: HashSet<&Vec<i64>> = points.iter().collect();
1741    if set.len() != points.len() {
1742        return Some(VerifyResult::fail("duplicate points"));
1743    }
1744    if !points
1745        .iter()
1746        .all(|p| p.len() == n && p.iter().all(|&x| x == 0 || x == 1))
1747    {
1748        return Some(VerifyResult::fail(format!("points not binary length-{n}")));
1749    }
1750    None
1751}
1752
1753/// A Sidon subset of `{0,1}^n` under componentwise integer addition: all
1754/// pairwise sums `a+b` (`a <= b`) distinct.
1755pub fn verify_sidon(points: &[Vec<i64>], n: usize) -> VerifyResult {
1756    if let Some(bad) = binary_points_ok(points, n) {
1757        return bad;
1758    }
1759    let m = points.len();
1760    if n <= 32 {
1761        let Some(pair_count) = m
1762            .checked_add(1)
1763            .and_then(|next| m.checked_mul(next))
1764            .map(|value| value / 2)
1765        else {
1766            return VerifyResult::fail("pairwise-sum count overflows this platform");
1767        };
1768        let expanded = points
1769            .iter()
1770            .map(|point| {
1771                point
1772                    .iter()
1773                    .enumerate()
1774                    .fold(0_u64, |packed, (index, value)| {
1775                        packed | ((*value as u64) << (2 * index))
1776                    })
1777            })
1778            .collect::<Vec<_>>();
1779        let mut sums = Vec::new();
1780        if sums.try_reserve_exact(pair_count).is_err() {
1781            return VerifyResult::fail("insufficient memory for pairwise-sum check");
1782        }
1783        for i in 0..m {
1784            for j in i..m {
1785                // Each coordinate occupies two bits and sums to at most two,
1786                // so ordinary integer addition cannot carry between lanes.
1787                sums.push(expanded[i] + expanded[j]);
1788            }
1789        }
1790        sums.sort_unstable();
1791        if sums.windows(2).any(|pair| pair[0] == pair[1]) {
1792            return VerifyResult::fail("pairwise-sum collision (not Sidon)");
1793        }
1794        return VerifyResult::ok(format!(
1795            "Sidon verified: {m} points, {pair_count} pairwise sums all distinct"
1796        ));
1797    }
1798    let mut sums: HashSet<Vec<i64>> = HashSet::new();
1799    let mut count = 0usize;
1800    for i in 0..m {
1801        for j in i..m {
1802            let s: Vec<i64> = (0..n).map(|k| points[i][k] + points[j][k]).collect();
1803            if !sums.insert(s) {
1804                return VerifyResult::fail("pairwise-sum collision (not Sidon)");
1805            }
1806            count += 1;
1807        }
1808    }
1809    VerifyResult::ok(format!(
1810        "Sidon verified: {m} points, {count} pairwise sums all distinct"
1811    ))
1812}
1813
1814/// Verify a Sidon set in `GF(2)^n` (OEIS A394031): `elements` are integer
1815/// bitmasks; the set is Sidon iff the elements are distinct and all pairwise
1816/// XORs are distinct and nonzero (equivalently, no four distinct elements XOR
1817/// to zero). Mirrors the reference `is_gf2_sidon`; pure integer arithmetic.
1818#[must_use]
1819pub fn verify_gf2_sidon(elements: &[u64]) -> VerifyResult {
1820    let m = elements.len();
1821    let distinct: HashSet<u64> = elements.iter().copied().collect();
1822    if distinct.len() != m {
1823        return VerifyResult::fail("duplicate element (not a set)");
1824    }
1825    let mut xors: HashSet<u64> = HashSet::new();
1826    let mut count = 0usize;
1827    for i in 0..m {
1828        for j in (i + 1)..m {
1829            let x = elements[i] ^ elements[j];
1830            if x == 0 {
1831                return VerifyResult::fail("zero XOR (equal elements)");
1832            }
1833            if !xors.insert(x) {
1834                return VerifyResult::fail("pairwise-XOR collision (not a GF(2) Sidon set)");
1835            }
1836            count += 1;
1837        }
1838    }
1839    VerifyResult::ok(format!(
1840        "GF(2)-Sidon verified: {m} elements, {count} pairwise XORs all distinct"
1841    ))
1842}
1843
1844/// Greatest common divisor of two non-negative integers (0 maps to 1 so a
1845/// normalized direction class is always well-defined).
1846fn gcd_pos(a: i64, b: i64) -> i64 {
1847    let (mut a, mut b) = (a.abs(), b.abs());
1848    while b != 0 {
1849        let t = b;
1850        b = a % b;
1851        a = t;
1852    }
1853    if a == 0 { 1 } else { a }
1854}
1855
1856/// Verify a union-free family (OEIS A347025): `sets` are nonempty subsets of
1857/// `{1..n}` and no member is the union of a sub-collection of the others.
1858/// Polynomial check: a member C is expressible iff the union of every OTHER
1859/// member that is a subset of C equals C (any super-C member would overshoot).
1860/// Certifies the lower bound a(n) >= |sets| only.
1861#[must_use]
1862pub fn verify_union_free(n: usize, sets: &[Vec<u32>]) -> VerifyResult {
1863    if n == 0 || n > 63 {
1864        return VerifyResult::fail("n out of range (1..=63)");
1865    }
1866    let mut masks: Vec<u64> = Vec::with_capacity(sets.len());
1867    for s in sets {
1868        if s.is_empty() {
1869            return VerifyResult::fail("empty set (members must be nonempty)");
1870        }
1871        let mut m = 0u64;
1872        for &e in s {
1873            if e < 1 || (e as usize) > n {
1874                return VerifyResult::fail(format!("element {e} out of {{1..{n}}}"));
1875            }
1876            m |= 1u64 << (e - 1);
1877        }
1878        masks.push(m);
1879    }
1880    let distinct: HashSet<u64> = masks.iter().copied().collect();
1881    if distinct.len() != masks.len() {
1882        return VerifyResult::fail("duplicate set (members must be distinct)");
1883    }
1884    for (i, &c) in masks.iter().enumerate() {
1885        let mut u = 0u64;
1886        for (j, &s) in masks.iter().enumerate() {
1887            if i != j && (s & c) == s {
1888                u |= s;
1889            }
1890        }
1891        if u == c {
1892            return VerifyResult::fail(
1893                "a member is the union of a sub-collection of the others (not union-free)",
1894            );
1895        }
1896    }
1897    VerifyResult::ok(format!(
1898        "union-free verified: {} sets over {{1..{n}}}, no member is a union of others",
1899        masks.len()
1900    ))
1901}
1902
1903/// Verify a non-attacking rook placement (OEIS A321531): `perm` is a
1904/// permutation of `1..=n` (one rook per row, distinct columns), and the count
1905/// of distinct direction classes `sorted(|Δcol|,|Δrow|)/gcd` over all rook
1906/// pairs equals `claimed` (when given). Certifies the lower bound a(n) >=
1907/// count only.
1908#[must_use]
1909pub fn verify_rook_directions(n: usize, perm: &[i64], claimed: Option<usize>) -> VerifyResult {
1910    if perm.len() != n {
1911        return VerifyResult::fail("perm length != n");
1912    }
1913    let mut seen = vec![false; n + 1];
1914    for &c in perm {
1915        if c < 1 || (c as usize) > n {
1916            return VerifyResult::fail("column out of 1..=n");
1917        }
1918        if seen[c as usize] {
1919            return VerifyResult::fail("repeated column (attacking rooks)");
1920        }
1921        seen[c as usize] = true;
1922    }
1923    let mut classes: HashSet<(i64, i64)> = HashSet::new();
1924    for i in 0..n {
1925        for j in (i + 1)..n {
1926            let drow = (j as i64) - (i as i64);
1927            let dcol = perm[j] - perm[i];
1928            let g = gcd_pos(dcol, drow);
1929            let (a, b) = (dcol.abs() / g, drow.abs() / g);
1930            classes.insert(if a <= b { (a, b) } else { (b, a) });
1931        }
1932    }
1933    let count = classes.len();
1934    if let Some(cl) = claimed
1935        && count != cl
1936    {
1937        return VerifyResult::fail(format!("direction count {count} != claimed {cl}"));
1938    }
1939    VerifyResult::ok(format!(
1940        "rook-directions verified: {n} non-attacking rooks realize {count} distinct direction classes"
1941    ))
1942}
1943
1944/// A Golomb ruler: integer marks with all `C(m,2)` pairwise differences
1945/// distinct.
1946/// Verify an Erdős #1056 cut-equality certificate: a prime `p` and
1947/// strictly increasing cuts `c_0 < ... < c_k` such that every consecutive
1948/// interval `(c_{i-1}, c_i]` has integer product `== 1 (mod p)`. Pure
1949/// modular arithmetic — deterministic and total, no search.
1950/// Erdős #617 witness shape: a balanced r-coloring of K_n. Checks that
1951/// every edge {i,j} (i<j, 0-indexed) is colored in 1..=r and that every
1952/// (r+1)-subset of vertices sees ALL r colors among its internal edges.
1953pub fn verify_balanced_coloring(
1954    n: usize,
1955    r: usize,
1956    edge_colors: &std::collections::BTreeMap<String, u32>,
1957) -> VerifyResult {
1958    if r < 2 || n < r + 1 {
1959        return VerifyResult::fail(format!("need r >= 2 and n >= r+1 (got n={n}, r={r})"));
1960    }
1961    // Dense lookup table from the string-keyed map.
1962    let mut color = vec![vec![0u32; n]; n];
1963    for (key, &c) in edge_colors {
1964        let Some((a, b)) = key.split_once(',') else {
1965            return VerifyResult::fail(format!("bad edge key '{key}' (want \"i,j\")"));
1966        };
1967        let (Ok(i), Ok(j)) = (a.trim().parse::<usize>(), b.trim().parse::<usize>()) else {
1968            return VerifyResult::fail(format!("bad edge key '{key}'"));
1969        };
1970        if i >= n || j >= n || i >= j {
1971            return VerifyResult::fail(format!("edge '{key}' out of range or not i<j for n={n}"));
1972        }
1973        if c == 0 || c as usize > r {
1974            return VerifyResult::fail(format!("edge '{key}' color {c} outside 1..={r}"));
1975        }
1976        color[i][j] = c;
1977    }
1978    for (i, row) in color.iter().enumerate() {
1979        for (j, &c) in row.iter().enumerate().skip(i + 1) {
1980            if c == 0 {
1981                return VerifyResult::fail(format!("edge {i},{j} is uncolored"));
1982            }
1983        }
1984    }
1985    // Every (r+1)-subset must see all r colors. Iterate subsets via a
1986    // simple combinations walker (k = r+1).
1987    let k = r + 1;
1988    let mut idx: Vec<usize> = (0..k).collect();
1989    let mut checked = 0u64;
1990    loop {
1991        let mut seen = vec![false; r + 1];
1992        for x in 0..k {
1993            for y in (x + 1)..k {
1994                seen[color[idx[x]][idx[y]] as usize] = true;
1995            }
1996        }
1997        if let Some(missing) = (1..=r).find(|&c| !seen[c]) {
1998            return VerifyResult::fail(format!("subset {:?} sees no edge of color {missing}", idx));
1999        }
2000        checked += 1;
2001        // next combination
2002        let mut pos = k;
2003        while pos > 0 {
2004            pos -= 1;
2005            if idx[pos] != pos + n - k {
2006                idx[pos] += 1;
2007                for q in (pos + 1)..k {
2008                    idx[q] = idx[q - 1] + 1;
2009                }
2010                break;
2011            }
2012            if pos == 0 {
2013                return VerifyResult::ok(format!(
2014                    "balanced {r}-coloring of K_{n} verified: {checked} {k}-subsets each see all {r} colors"
2015                ));
2016            }
2017        }
2018    }
2019}
2020
2021pub fn verify_interval_product(p: u64, cuts: &[u64]) -> VerifyResult {
2022    if !is_prime(p) {
2023        return VerifyResult::fail(format!("modulus p={p} must be prime"));
2024    }
2025    if cuts.len() < 2 {
2026        return VerifyResult::fail("need at least two cuts (one interval)");
2027    }
2028    for w in cuts.windows(2) {
2029        if w[0] >= w[1] {
2030            return VerifyResult::fail("cuts must be strictly increasing");
2031        }
2032    }
2033    for w in cuts.windows(2) {
2034        let mut prod: u64 = 1;
2035        for m in (w[0] + 1)..=w[1] {
2036            prod = ((prod as u128 * (m % p) as u128) % p as u128) as u64;
2037        }
2038        if prod != 1 {
2039            return VerifyResult::fail(format!(
2040                "interval ({}, {}] has product {prod} mod {p} != 1",
2041                w[0], w[1]
2042            ));
2043        }
2044    }
2045    VerifyResult::ok(format!(
2046        "Erdos #1056 certificate: prime p={p}, {} consecutive interval(s) each with product 1 mod p",
2047        cuts.len() - 1
2048    ))
2049}
2050
2051// --- shared exact number theory -------------------------------------------
2052
2053/// Number of carries when adding `a + b` in base `p` (Kummer's theorem:
2054/// this equals `v_p(C(a+b, a))`).
2055fn carries_base_p(mut a: u128, mut b: u128, p: u128) -> u64 {
2056    let mut carry: u128 = 0;
2057    let mut count: u64 = 0;
2058    while a > 0 || b > 0 || carry > 0 {
2059        let s = a % p + b % p + carry;
2060        carry = u128::from(s >= p);
2061        count += carry as u64;
2062        a /= p;
2063        b /= p;
2064    }
2065    count
2066}
2067
2068/// Legendre: `v_p(n!)`.
2069fn vp_factorial(n: u64, p: u64) -> u64 {
2070    let mut s = 0u64;
2071    let mut pk = p;
2072    while pk <= n {
2073        s += n / pk;
2074        pk = pk.saturating_mul(p);
2075    }
2076    s
2077}
2078
2079/// `v_p(C(n, k))` via Legendre.
2080fn vp_binom(n: u64, k: u64, p: u64) -> u64 {
2081    vp_factorial(n, p) - vp_factorial(k, p) - vp_factorial(n - k, p)
2082}
2083
2084/// `v_p(n)` for `n >= 1`.
2085fn vp_of(mut n: u64, p: u64) -> u64 {
2086    let mut v = 0u64;
2087    while n.is_multiple_of(p) {
2088        n /= p;
2089        v += 1;
2090    }
2091    v
2092}
2093
2094fn gcd_u64(mut a: u64, mut b: u64) -> u64 {
2095    while b != 0 {
2096        let t = a % b;
2097        a = b;
2098        b = t;
2099    }
2100    a
2101}
2102
2103/// Primes up to `n` inclusive (trial division; `n` is small here).
2104fn primes_upto(n: u64) -> Vec<u64> {
2105    (2..=n).filter(|&q| is_prime(q)).collect()
2106}
2107
2108/// Parse a decimal string into u128 (guard: 1..=38 digits, all ASCII).
2109fn parse_decimal_u128(s: &str) -> Result<u128, String> {
2110    if s.is_empty() || s.len() > 38 || !s.bytes().all(|b| b.is_ascii_digit()) {
2111        return Err(format!("`{s}` is not a 1..=38 digit decimal string"));
2112    }
2113    s.parse::<u128>().map_err(|e| format!("parse `{s}`: {e}"))
2114}
2115
2116/// A decimal string mod a small modulus, by digit streaming — handles
2117/// integers far beyond u128 without big-int arithmetic.
2118fn decimal_mod(s: &str, m: u64) -> Result<u64, String> {
2119    if s.is_empty() || !s.bytes().all(|b| b.is_ascii_digit()) {
2120        return Err(format!("`{s}` is not a decimal string"));
2121    }
2122    let mut acc: u64 = 0;
2123    for b in s.bytes() {
2124        acc = (acc * 10 + u64::from(b - b'0')) % m;
2125    }
2126    Ok(acc)
2127}
2128
2129/// Multiplicative order of `base` mod prime `p` (`base` not divisible
2130/// by `p`); iterates at most `p - 1` steps.
2131fn multiplicative_order(base: u64, p: u64) -> Result<u64, String> {
2132    if base.is_multiple_of(p) {
2133        return Err(format!("{base} is 0 mod {p}; order undefined"));
2134    }
2135    let mut acc = base % p;
2136    let mut ord = 1u64;
2137    while acc != 1 {
2138        acc = acc * base % p;
2139        ord += 1;
2140        if ord >= p {
2141            return Err(format!("order of {base} mod {p} did not divide p-1"));
2142        }
2143    }
2144    Ok(ord)
2145}
2146
2147// --- Erdős #203: partial CRT cover ----------------------------------------
2148
2149/// Verify an Erdős #203 partial CRT covering certificate. `m` is a
2150/// decimal string coprime to 6; each row pins a prime `p`, the orders of
2151/// 2 and 3 mod `p`, `h = lcm(ord2, ord3)`, `t_p = (-m^-1) mod p`,
2152/// `m mod p`, and an affine line such that `p | 2^k 3^l m + 1` iff
2153/// `alpha*k + beta*l == gamma (mod h)` — checked exhaustively over
2154/// `(k, l) in [0, h)^2`. Deterministic and total.
2155pub fn verify_crt_partial_cover(m: &str, rows: &[CrtCoverRow]) -> VerifyResult {
2156    if rows.is_empty() {
2157        return VerifyResult::fail("need at least one prime row");
2158    }
2159    match (decimal_mod(m, 2), decimal_mod(m, 3)) {
2160        (Ok(r2), Ok(r3)) => {
2161            if r2 == 0 || r3 == 0 {
2162                return VerifyResult::fail("m must be coprime to 6");
2163            }
2164        }
2165        (Err(e), _) | (_, Err(e)) => return VerifyResult::fail(e),
2166    }
2167    for row in rows {
2168        let p = row.p;
2169        if !(5..=1_000_000).contains(&p) || !is_prime(p) {
2170            return VerifyResult::fail(format!("row p={p} must be a prime in [5, 10^6]"));
2171        }
2172        let ord2 = match multiplicative_order(2, p) {
2173            Ok(v) => v,
2174            Err(e) => return VerifyResult::fail(e),
2175        };
2176        let ord3 = match multiplicative_order(3, p) {
2177            Ok(v) => v,
2178            Err(e) => return VerifyResult::fail(e),
2179        };
2180        if ord2 != row.ord2 || ord3 != row.ord3 {
2181            return VerifyResult::fail(format!(
2182                "row p={p}: ord(2)={ord2}, ord(3)={ord3} != claimed ({}, {})",
2183                row.ord2, row.ord3
2184            ));
2185        }
2186        let h = ord2 / gcd_u64(ord2, ord3) * ord3;
2187        if h != row.h || row.line[3] != h {
2188            return VerifyResult::fail(format!(
2189                "row p={p}: lcm(ord2, ord3)={h} != claimed h={} / line modulus {}",
2190                row.h, row.line[3]
2191            ));
2192        }
2193        if h > 5_000 {
2194            return VerifyResult::fail(format!("row p={p}: h={h} exceeds the 5000 guard"));
2195        }
2196        let mm = match decimal_mod(m, p) {
2197            Ok(v) => v,
2198            Err(e) => return VerifyResult::fail(e),
2199        };
2200        if mm != row.m_mod_p || mm == 0 {
2201            return VerifyResult::fail(format!(
2202                "row p={p}: m mod p = {mm} != claimed {} (and must be nonzero)",
2203                row.m_mod_p
2204            ));
2205        }
2206        let t = (p - mod_pow(mm, p - 2, p)) % p;
2207        if t != row.t_p {
2208            return VerifyResult::fail(format!(
2209                "row p={p}: (-m^-1) mod p = {t} != claimed t_p={}",
2210                row.t_p
2211            ));
2212        }
2213        let (al, be, ga) = (row.line[0], row.line[1], row.line[2]);
2214        for k in 0..h {
2215            for l in 0..h {
2216                let lhs = (mod_pow(2, k, p) * mod_pow(3, l, p) % p * mm % p + 1).is_multiple_of(p);
2217                let rhs = (al * k + be * l) % h == ga % h; // affine line mod h
2218                if lhs != rhs {
2219                    return VerifyResult::fail(format!(
2220                        "row p={p}: congruence line fails at (k, l) = ({k}, {l})"
2221                    ));
2222                }
2223            }
2224        }
2225    }
2226    VerifyResult::ok(format!(
2227        "Erdos #203 partial CRT cover: m coprime to 6, {} prime row(s) verified (p | 2^k 3^l m + 1 <=> affine line mod h)",
2228        rows.len()
2229    ))
2230}
2231
2232// --- Erdős #684: Kummer no-carry lower bound -------------------------------
2233
2234/// Verify an Erdős #684 certificate: for each `(k, m)`, recompute
2235/// `m = prod_{p<=k} p^(floor(log_p k)+1)` and confirm zero Kummer carries
2236/// adding `j + (m-1-j)` in base `p` for all `2 <= j <= k`, `p <= j` —
2237/// hence no prime `p <= j` divides `C(m-1, j)` and `f(m-1) > k`.
2238pub fn verify_kummer_no_carry(entries: &[KummerEntry]) -> VerifyResult {
2239    if entries.is_empty() {
2240        return VerifyResult::fail("need at least one (k, m) entry");
2241    }
2242    for e in entries {
2243        let k = e.k;
2244        if !(3..=20).contains(&k) {
2245            return VerifyResult::fail(format!("k={k} outside the [3, 20] guard"));
2246        }
2247        let mut m: u64 = 1;
2248        for p in primes_upto(k) {
2249            let mut pe = 1u64;
2250            let mut exp = 0u64;
2251            while pe * p <= k {
2252                pe *= p;
2253                exp += 1;
2254            }
2255            for _ in 0..=exp {
2256                m = match m.checked_mul(p) {
2257                    Some(v) => v,
2258                    None => return VerifyResult::fail(format!("M_{k} overflows u64")),
2259                };
2260            }
2261        }
2262        if m != e.m {
2263            return VerifyResult::fail(format!("k={k}: recomputed M_k={m} != claimed {}", e.m));
2264        }
2265        let n = m - 1;
2266        for j in 2..=k {
2267            for p in primes_upto(j) {
2268                if carries_base_p(u128::from(j), u128::from(n - j), u128::from(p)) != 0 {
2269                    return VerifyResult::fail(format!(
2270                        "k={k}: carry adding {j} + (M-1-{j}) base {p} — C(M-1, {j}) not p-free"
2271                    ));
2272                }
2273            }
2274        }
2275    }
2276    VerifyResult::ok(format!(
2277        "Erdos #684 certificate: f(M_k - 1) > k verified for {} value(s) of k (zero Kummer carries)",
2278        entries.len()
2279    ))
2280}
2281
2282// --- Erdős #700: min gcd(n, C(n,k)) ----------------------------------------
2283
2284/// Verify an Erdős #700 value certificate: for each `(n, f)`, recompute
2285/// `f(n) = min_{1<k<=n/2} gcd(n, C(n,k))` via the Kummer identity
2286/// `gcd(n, C(n,k)) = prod_{p|n} p^min(v_p(n), carries_p(k, n-k))`.
2287pub fn verify_min_binom_gcd(cases: &[MinGcdCase]) -> VerifyResult {
2288    if cases.is_empty() {
2289        return VerifyResult::fail("need at least one (n, f) case");
2290    }
2291    for c in cases {
2292        let n = c.n;
2293        if !(4..=10_000).contains(&n) {
2294            return VerifyResult::fail(format!("n={n} outside the [4, 10000] guard"));
2295        }
2296        let mut factors: Vec<(u64, u64)> = Vec::new();
2297        let mut rem = n;
2298        let mut p = 2u64;
2299        while p * p <= rem {
2300            if rem.is_multiple_of(p) {
2301                factors.push((p, vp_of(rem, p)));
2302                while rem.is_multiple_of(p) {
2303                    rem /= p;
2304                }
2305            }
2306            p += 1;
2307        }
2308        if rem > 1 {
2309            factors.push((rem, 1));
2310        }
2311        let mut best = u64::MAX;
2312        for k in 2..=n / 2 {
2313            let mut g = 1u64;
2314            for &(p, vn) in &factors {
2315                let carries = carries_base_p(u128::from(k), u128::from(n - k), u128::from(p));
2316                g *= p.pow(vn.min(carries) as u32);
2317            }
2318            best = best.min(g);
2319        }
2320        if best != c.f {
2321            return VerifyResult::fail(format!("n={n}: recomputed f(n)={best} != claimed {}", c.f));
2322        }
2323    }
2324    VerifyResult::ok(format!(
2325        "Erdos #700 certificate: f(n) = min gcd(n, C(n,k)) verified for {} case(s)",
2326        cases.len()
2327    ))
2328}
2329
2330// --- Erdős #1093: ELS93 deficiency -----------------------------------------
2331
2332/// Does `x | i * C(k, i)`? Every prime factor of `i * C(k, i)` is `<= k`,
2333/// so trial-divide `x` by primes `<= k`; a residual `> 1` means no.
2334/// Otherwise check `v_p(i) + v_p(C(k,i)) >= e` for each `p^e || x` —
2335/// `i * C(k, i)` itself is never materialized.
2336fn divides_smooth(mut x: u128, i: u64, k: u64) -> bool {
2337    for p in primes_upto(k) {
2338        if x == 1 {
2339            break;
2340        }
2341        let pp = u128::from(p);
2342        let mut e = 0u64;
2343        while x.is_multiple_of(pp) {
2344            x /= pp;
2345            e += 1;
2346        }
2347        if e > 0 && vp_of(i, p) + vp_binom(k, i, p) < e {
2348            return false;
2349        }
2350    }
2351    x == 1
2352}
2353
2354/// Verify an Erdős #1093 (ELS93) deficiency certificate: each entry's
2355/// `C(N,k)` is Kummer-defined and `delta(N,k)` (and slot positions, when
2356/// given) recompute exactly. `N` may be up to 38 decimal digits.
2357pub fn verify_binom_deficiency(entries: &[DeficiencyEntry]) -> VerifyResult {
2358    if entries.is_empty() {
2359        return VerifyResult::fail("need at least one entry");
2360    }
2361    for e in entries {
2362        let k = e.k;
2363        if !(2..=150).contains(&k) {
2364            return VerifyResult::fail(format!("k={k} outside the [2, 150] guard"));
2365        }
2366        let n = match parse_decimal_u128(&e.n) {
2367            Ok(v) => v,
2368            Err(err) => return VerifyResult::fail(err),
2369        };
2370        if n < 2 * u128::from(k) {
2371            return VerifyResult::fail(format!("entry k={k}: need N >= 2k"));
2372        }
2373        for p in primes_upto(k) {
2374            if carries_base_p(u128::from(k), n - u128::from(k), u128::from(p)) != 0 {
2375                return VerifyResult::fail(format!(
2376                    "entry k={k}: prime {p} divides C(N,k) — not Kummer-defined"
2377                ));
2378            }
2379        }
2380        let mut slots: Vec<u64> = Vec::new();
2381        for i in 1..=k {
2382            let x = n - u128::from(k) + u128::from(i);
2383            if divides_smooth(x, i, k) {
2384                slots.push(i);
2385            }
2386        }
2387        if slots.len() as u64 != e.delta {
2388            return VerifyResult::fail(format!(
2389                "entry k={k}: recomputed delta={} != claimed {}",
2390                slots.len(),
2391                e.delta
2392            ));
2393        }
2394        if let Some(claimed) = &e.slots
2395            && &slots != claimed
2396        {
2397            return VerifyResult::fail(format!(
2398                "entry k={k}: smooth slots {slots:?} != claimed {claimed:?}"
2399            ));
2400        }
2401    }
2402    VerifyResult::ok(format!(
2403        "Erdos #1093 deficiency certificate: {} entr(ies) Kummer-defined with delta and slots recomputed exactly",
2404        entries.len()
2405    ))
2406}
2407
2408// --- Erdős #1094: exception enumeration ------------------------------------
2409
2410/// `C(k, r)` for `k <= 40` — exact in u64.
2411fn binom_u64(k: u64, r: u64) -> u64 {
2412    let r = r.min(k - r);
2413    let mut res = 1u64;
2414    for i in 1..=r {
2415        res = res * (k - r + i) / i;
2416    }
2417    res
2418}
2419
2420/// All divisors of `g`, where `g | lcm(1..k)` so every prime factor is
2421/// `<= k`. Returns None if `g` does not fully factor over primes `<= k`
2422/// or the divisor count exceeds the guard.
2423fn divisors_smooth(g: u64, k: u64) -> Option<Vec<u64>> {
2424    let mut rem = g;
2425    let mut pf: Vec<(u64, u64)> = Vec::new();
2426    for p in primes_upto(k) {
2427        if rem.is_multiple_of(p) {
2428            pf.push((p, vp_of(rem, p)));
2429            while rem.is_multiple_of(p) {
2430                rem /= p;
2431            }
2432        }
2433    }
2434    if rem != 1 {
2435        return None;
2436    }
2437    let mut divs: Vec<u64> = vec![1];
2438    for (p, e) in pf {
2439        let prev = divs.clone();
2440        let mut pe = 1u64;
2441        for _ in 0..e {
2442            pe *= p;
2443            for d in &prev {
2444                divs.push(d * pe);
2445            }
2446        }
2447        if divs.len() > 200_000 {
2448            return None;
2449        }
2450    }
2451    Some(divs)
2452}
2453
2454/// Is `(N, k)` a #1094 exception — no prime `p <= max(N/k, k)` divides
2455/// `C(N, k)`? Early-exits on the first dividing prime. Returns None
2456/// (fail-closed) if a candidate survives past the 10^7 prime guard
2457/// without a verdict — that can only happen for a would-be NEW
2458/// exception, where refusing to claim is the correct behavior.
2459fn is_exception_guarded(n: u64, k: u64) -> Option<bool> {
2460    let mut p = 2u64;
2461    // Condition `p <= max(N/k, k)` without floats: p <= k || p*k <= N.
2462    while p <= k || p.saturating_mul(k) <= n {
2463        if is_prime(p) && vp_binom(n, k, p) > 0 {
2464            return Some(false);
2465        }
2466        if p > 10_000_000 {
2467            return None;
2468        }
2469        p += 1;
2470    }
2471    Some(true)
2472}
2473
2474/// Verify an Erdős #1094 exception-enumeration certificate: re-enumerate
2475/// every candidate `N = x + k - r` (`x | gcd(lcm(1..k), r*C(k,r))`,
2476/// `k | x`, `N >= 2k`) for `k <= k_max` and confirm the exception set
2477/// equals the claimed `(N, k)` list exactly.
2478pub fn verify_binom_exception_enum(k_max: u64, exceptions: &[(u64, u64)]) -> VerifyResult {
2479    if !(3..=40).contains(&k_max) {
2480        return VerifyResult::fail(format!("k_max={k_max} outside the [3, 40] guard"));
2481    }
2482    let claimed: std::collections::BTreeSet<(u64, u64)> = exceptions.iter().copied().collect();
2483    for &(n, k) in &claimed {
2484        if k > k_max || n < 2 * k {
2485            return VerifyResult::fail(format!(
2486                "claimed exception (N={n}, k={k}) outside k <= k_max / N >= 2k"
2487            ));
2488        }
2489    }
2490    let mut found: std::collections::BTreeSet<(u64, u64)> = std::collections::BTreeSet::new();
2491    let mut lambda: u64 = 1;
2492    let mut candidates: u64 = 0;
2493    for k in 2..=k_max {
2494        lambda = lambda / gcd_u64(lambda, k) * k;
2495        for r in 1..=k {
2496            let g = gcd_u64(lambda, r * binom_u64(k, r));
2497            let divs = match divisors_smooth(g, k) {
2498                Some(d) => d,
2499                None => {
2500                    return VerifyResult::fail(format!(
2501                        "divisor enumeration guard exceeded at k={k}, r={r}"
2502                    ));
2503                }
2504            };
2505            for x in divs {
2506                if !x.is_multiple_of(k) {
2507                    continue;
2508                }
2509                let n = x + k - r;
2510                if n < 2 * k {
2511                    continue;
2512                }
2513                candidates += 1;
2514                match is_exception_guarded(n, k) {
2515                    Some(true) => {
2516                        found.insert((n, k));
2517                    }
2518                    Some(false) => {}
2519                    None => {
2520                        return VerifyResult::fail(format!(
2521                            "exception test guard exceeded at (N={n}, k={k}) — refusing to claim"
2522                        ));
2523                    }
2524                }
2525            }
2526        }
2527    }
2528    if found != claimed {
2529        let extra: Vec<_> = found.difference(&claimed).collect();
2530        let missing: Vec<_> = claimed.difference(&found).collect();
2531        return VerifyResult::fail(format!(
2532            "exception set mismatch: extra {extra:?}, missing {missing:?}"
2533        ));
2534    }
2535    VerifyResult::ok(format!(
2536        "Erdos #1094 enumeration: {candidates} candidate(s) checked for k <= {k_max}; exception set of {} matches exactly",
2537        claimed.len()
2538    ))
2539}
2540
2541// --- UNSAT certificate (LRAT / RUP) ----------------------------------------
2542
2543/// Check that adding clause `c` is justified by reverse unit propagation
2544/// over the antecedent `hints` (in order) against `db`. Returns true iff
2545/// propagating `¬c` through the hinted clauses reaches a conflict — i.e.
2546/// `c` is RUP-implied by the current clause set. Hints that are satisfied,
2547/// non-unit, or unknown are rejected (a malformed proof never passes).
2548/// RAT check on the step's FIRST literal (the LRAT convention): the
2549/// step is a Resolution Asymmetric Tautology iff for every db clause D
2550/// containing the negated pivot, the resolvent (step ∪ D minus the
2551/// pivot pair) is RUP using the hints the step supplies for D's id.
2552/// Tautological resolvents pass vacuously. A clause with -pivot that
2553/// has no supplied hints fails the whole step — nothing is guessed.
2554fn rat_check(step: &LratStep, db: &std::collections::HashMap<u64, Vec<i64>>) -> bool {
2555    let Some(&pivot) = step.literals.first() else {
2556        return false; // the empty clause can never be RAT
2557    };
2558    let supplied: std::collections::HashMap<u64, &Vec<u64>> =
2559        step.rat_hints.iter().map(|(id, h)| (*id, h)).collect();
2560    for (&cid, clause) in db {
2561        if !clause.contains(&-pivot) {
2562            continue;
2563        }
2564        let mut resolvent: Vec<i64> = step.literals.clone();
2565        for &l in clause {
2566            if l != -pivot && l != 0 && !resolvent.contains(&l) {
2567                resolvent.push(l);
2568            }
2569        }
2570        if resolvent.iter().any(|&l| resolvent.contains(&-l) && l > 0) {
2571            continue; // tautological resolvent: vacuously implied
2572        }
2573        let Some(hints) = supplied.get(&cid) else {
2574            return false;
2575        };
2576        if !rup_checks(&resolvent, hints, db) {
2577            return false;
2578        }
2579    }
2580    true
2581}
2582
2583fn rup_checks(c: &[i64], hints: &[u64], db: &std::collections::HashMap<u64, Vec<i64>>) -> bool {
2584    // Falsify every literal of c: var |l| takes the value that makes l false.
2585    let mut assign: std::collections::HashMap<i64, bool> = std::collections::HashMap::new();
2586    for &l in c {
2587        if l == 0 {
2588            return false;
2589        }
2590        let v = l.abs();
2591        let want = l < 0; // l<0 ⇒ var true makes l false
2592        if let Some(&prev) = assign.get(&v)
2593            && prev != want
2594        {
2595            return false; // c is a tautology (l and ¬l) — not a real clause
2596        }
2597        assign.insert(v, want);
2598    }
2599    for &h in hints {
2600        let Some(cl) = db.get(&h) else {
2601            return false; // unknown antecedent
2602        };
2603        let mut unassigned: Vec<i64> = Vec::new();
2604        let mut satisfied = false;
2605        for &l in cl {
2606            if l == 0 {
2607                continue;
2608            }
2609            match assign.get(&l.abs()) {
2610                None => unassigned.push(l),
2611                Some(&val) => {
2612                    // l true under assign? l>0 wants var true; l<0 wants var false.
2613                    if (l > 0) == val {
2614                        satisfied = true;
2615                    }
2616                }
2617            }
2618        }
2619        if satisfied {
2620            return false; // a satisfied antecedent can neither propagate nor conflict
2621        }
2622        match unassigned.len() {
2623            0 => return true, // all literals falsified ⇒ conflict ⇒ c is RUP
2624            1 => {
2625                let l = unassigned[0];
2626                assign.insert(l.abs(), l > 0); // propagate the forced literal
2627            }
2628            _ => return false, // not unit ⇒ this hint cannot fire
2629        }
2630    }
2631    false // ran out of hints without a conflict
2632}
2633
2634/// Verify an UNSAT certificate: replay the LRAT proof over the CNF and
2635/// confirm it derives the empty clause. Each step's added clause must be
2636/// RUP-implied by the clauses available so far (original + previously
2637/// added). Deterministic and total; bounded by explicit guards.
2638pub fn verify_unsat_cert(cnf: &[Vec<i64>], proof: &[LratStep]) -> VerifyResult {
2639    if cnf.is_empty() {
2640        return VerifyResult::fail("empty CNF: nothing to refute");
2641    }
2642    if cnf.len() > 5_000_000 || proof.len() > 20_000_000 {
2643        return VerifyResult::fail("certificate exceeds the size guard");
2644    }
2645    let mut db: std::collections::HashMap<u64, Vec<i64>> = std::collections::HashMap::new();
2646    for (i, clause) in cnf.iter().enumerate() {
2647        let id = (i + 1) as u64; // original clauses are 1-indexed
2648        if db.insert(id, clause.clone()).is_some() {
2649            return VerifyResult::fail(format!("duplicate clause id {id}"));
2650        }
2651    }
2652    let mut derived_empty = false;
2653    for step in proof {
2654        if step.id == 0 {
2655            return VerifyResult::fail("proof clause id 0 is reserved");
2656        }
2657        if !rup_checks(&step.literals, &step.hints, &db) && !rat_check(step, &db) {
2658            return VerifyResult::fail(format!(
2659                "LRAT step {} is neither RUP-implied nor RAT on its first literal",
2660                step.id
2661            ));
2662        }
2663        let empty = step.literals.is_empty();
2664        if db.insert(step.id, step.literals.clone()).is_some() {
2665            return VerifyResult::fail(format!("clause id {} added twice", step.id));
2666        }
2667        if empty {
2668            derived_empty = true;
2669            break;
2670        }
2671    }
2672    if !derived_empty {
2673        return VerifyResult::fail("proof never derives the empty clause (UNSAT not established)");
2674    }
2675    VerifyResult::ok(format!(
2676        "UNSAT certificate: {} clause(s), {} LRAT step(s), empty clause derived by RUP",
2677        cnf.len(),
2678        proof.len()
2679    ))
2680}
2681
2682pub fn verify_golomb(marks: &[i64]) -> VerifyResult {
2683    let set: HashSet<&i64> = marks.iter().collect();
2684    if set.len() != marks.len() {
2685        return VerifyResult::fail("duplicate marks");
2686    }
2687    let mut diffs: HashSet<i64> = HashSet::new();
2688    let mut count = 0usize;
2689    for i in 0..marks.len() {
2690        for j in (i + 1)..marks.len() {
2691            if !diffs.insert((marks[j] - marks[i]).abs()) {
2692                return VerifyResult::fail("repeated pairwise difference (not a Golomb ruler)");
2693            }
2694            count += 1;
2695        }
2696    }
2697    let (lo, hi) = (marks.iter().min().copied(), marks.iter().max().copied());
2698    let length = match (lo, hi) {
2699        (Some(a), Some(b)) => b - a,
2700        _ => 0,
2701    };
2702    VerifyResult::ok(format!(
2703        "Golomb ruler: {} marks, length {length}, all {count} differences distinct",
2704        marks.len()
2705    ))
2706}
2707
2708/// A cap in `F_3^n`: no three distinct points sum to 0 mod 3 (no three
2709/// collinear). For each pair, the unique line-completion must be absent.
2710pub fn verify_cap(points: &[Vec<i64>], n: usize) -> VerifyResult {
2711    let set: HashSet<&Vec<i64>> = points.iter().collect();
2712    if set.len() != points.len() {
2713        return VerifyResult::fail("duplicate points");
2714    }
2715    if !points
2716        .iter()
2717        .all(|p| p.len() == n && p.iter().all(|&x| (0..=2).contains(&x)))
2718    {
2719        return VerifyResult::fail(format!("points not in (0,1,2)^{n}"));
2720    }
2721    let owned: HashSet<Vec<i64>> = points.iter().cloned().collect();
2722    let m = points.len();
2723    for i in 0..m {
2724        let a = &points[i];
2725        for b in points.iter().take(m).skip(i + 1) {
2726            let c: Vec<i64> = (0..n).map(|k| (-(a[k] + b[k])).rem_euclid(3)).collect();
2727            if owned.contains(&c) && &c != a && &c != b {
2728                return VerifyResult::fail("3 collinear points found (not a cap)");
2729            }
2730        }
2731    }
2732    VerifyResult::ok(format!(
2733        "cap verified: {m} points in F_3^{n}, no 3 collinear"
2734    ))
2735}
2736
2737/// A `B_h` set in `{0,1}^n`: all sums of `h` elements (with repetition,
2738/// non-decreasing index order) distinct. `h = 2` is Sidon.
2739pub fn verify_bh(points: &[Vec<i64>], n: usize, h: usize) -> VerifyResult {
2740    if let Some(bad) = binary_points_ok(points, n) {
2741        return bad;
2742    }
2743    let m = points.len();
2744    if m == 0 || h == 0 {
2745        return VerifyResult::ok(format!("B_{h} verified: {m} points, 0 sums"));
2746    }
2747    let mut sums: HashSet<Vec<i64>> = HashSet::new();
2748    let mut count = 0usize;
2749    let mut idx = vec![0usize; h];
2750    loop {
2751        let mut s = vec![0i64; n];
2752        for &i in &idx {
2753            for k in 0..n {
2754                s[k] += points[i][k];
2755            }
2756        }
2757        if !sums.insert(s) {
2758            return VerifyResult::fail(format!("B_{h} violated: a repeated {h}-fold sum"));
2759        }
2760        count += 1;
2761        if !advance_with_replacement(&mut idx, m) {
2762            break;
2763        }
2764    }
2765    VerifyResult::ok(format!(
2766        "B_{h} verified: {m} points, {count} h-fold sums all distinct"
2767    ))
2768}
2769
2770/// A covering design `C(v, k, t)`: blocks are `k`-subsets of `[0, v)`
2771/// such that every `t`-subset of `[0, v)` is contained in at least one.
2772pub fn verify_covering(blocks: &[Vec<usize>], v: usize, k: usize, t: usize) -> VerifyResult {
2773    let norm: Vec<Vec<usize>> = blocks
2774        .iter()
2775        .map(|b| {
2776            let s: std::collections::BTreeSet<usize> = b.iter().copied().collect();
2777            s.into_iter().collect()
2778        })
2779        .collect();
2780    if !norm
2781        .iter()
2782        .all(|b| b.len() == k && b.iter().all(|&x| x < v))
2783    {
2784        return VerifyResult::fail(format!("blocks not valid {k}-subsets of [0,{v})"));
2785    }
2786    let mut covered: HashSet<Vec<usize>> = HashSet::new();
2787    for b in &norm {
2788        each_combination(b.len(), t, &mut |sub| {
2789            covered.insert(sub.iter().map(|&i| b[i]).collect());
2790        });
2791    }
2792    let mut need = 0usize;
2793    let mut missing = 0usize;
2794    each_combination(v, t, &mut |sub| {
2795        need += 1;
2796        if !covered.contains(sub) {
2797            missing += 1;
2798        }
2799    });
2800    if missing > 0 {
2801        return VerifyResult::fail(format!(
2802            "not a covering: {missing} of {need} t-subsets uncovered"
2803        ));
2804    }
2805    VerifyResult::ok(format!(
2806        "valid C({v},{k},{t}) covering with {} blocks",
2807        norm.len()
2808    ))
2809}
2810
2811/// A constant-weight binary code `A(n, d, w)`: codewords of weight
2812/// exactly `w`, pairwise Hamming distance `>= d`.
2813pub fn verify_constant_weight(words: &[Vec<i64>], n: usize, d: usize, w: usize) -> VerifyResult {
2814    let set: HashSet<&Vec<i64>> = words.iter().collect();
2815    if set.len() != words.len() {
2816        return VerifyResult::fail("duplicate codewords");
2817    }
2818    if !words
2819        .iter()
2820        .all(|c| c.len() == n && c.iter().all(|&x| x == 0 || x == 1))
2821    {
2822        return VerifyResult::fail(format!("words not binary length-{n}"));
2823    }
2824    if let Some(c) = words.iter().find(|c| c.iter().sum::<i64>() as usize != w) {
2825        return VerifyResult::fail(format!(
2826            "a codeword has weight {} != {w}",
2827            c.iter().sum::<i64>()
2828        ));
2829    }
2830    for i in 0..words.len() {
2831        for j in (i + 1)..words.len() {
2832            let dist = (0..n).filter(|&k| words[i][k] != words[j][k]).count();
2833            if dist < d {
2834                return VerifyResult::fail(format!("a pair has Hamming distance {dist} < {d}"));
2835            }
2836        }
2837    }
2838    VerifyResult::ok(format!(
2839        "constant-weight code A({n},{d},{w}): {} words, all weight {w}, min dist >= {d}",
2840        words.len()
2841    ))
2842}
2843
2844/// A Costas array: a permutation `p` of consecutive integers such that
2845/// the displacement vectors `(j-i, p[j]-p[i])` for `i < j` are distinct.
2846pub fn verify_costas(perm: &[i64]) -> VerifyResult {
2847    let n = perm.len();
2848    let mut sorted = perm.to_vec();
2849    sorted.sort_unstable();
2850    let min = perm.iter().min().copied().unwrap_or(0);
2851    let expected: Vec<i64> = (0..n as i64).map(|i| min + i).collect();
2852    if sorted != expected {
2853        return VerifyResult::fail("not a permutation");
2854    }
2855    let mut vecs: HashSet<(i64, i64)> = HashSet::new();
2856    let mut count = 0usize;
2857    for i in 0..n {
2858        for j in (i + 1)..n {
2859            if !vecs.insert(((j - i) as i64, perm[j] - perm[i])) {
2860                return VerifyResult::fail("repeated displacement vector (not a Costas array)");
2861            }
2862            count += 1;
2863        }
2864    }
2865    VerifyResult::ok(format!(
2866        "Costas array of order {n} verified ({count} displacement vectors all distinct)"
2867    ))
2868}
2869
2870/// A linear `[n, k, d]_q` code given by a `k x n` generator matrix over a
2871/// prime field `GF(q)`. Verifies `rank(G) = k` and that the true minimum
2872/// distance (min nonzero codeword weight, by exhaustive enumeration of
2873/// the `q^k` codewords, guarded) is `>= claimed_d`. Prime-power `GF(q)`
2874/// is refused rather than mis-verified.
2875// Frozen exact verifier: the range loops index multiple parallel arrays
2876// (codeword/weight); the explicit index is the faithful expression, not a
2877// refactor target.
2878#[allow(clippy::needless_range_loop)]
2879pub fn verify_linear_code(generator: &[Vec<i64>], q: u64, claimed_d: usize) -> VerifyResult {
2880    const MAX_ENUM: u64 = 1_000_000;
2881    if !is_prime(q) {
2882        return VerifyResult::fail(format!(
2883            "q={q} not prime; prime-power GF(q) not implemented — refusing to claim"
2884        ));
2885    }
2886    let k = generator.len();
2887    if k == 0 {
2888        return VerifyResult::fail("empty generator");
2889    }
2890    let n = generator[0].len();
2891    if !generator.iter().all(|row| row.len() == n) {
2892        return VerifyResult::fail("ragged generator matrix");
2893    }
2894    let g: Vec<Vec<u64>> = generator
2895        .iter()
2896        .map(|row| row.iter().map(|&x| x.rem_euclid(q as i64) as u64).collect())
2897        .collect();
2898    if gf_rank(&g, q) != k {
2899        return VerifyResult::fail(format!(
2900            "generator rank < k={k} (rows dependent — not an [n,{k}] code)"
2901        ));
2902    }
2903    let qk = (q).checked_pow(k as u32);
2904    match qk {
2905        Some(v) if v <= MAX_ENUM => {}
2906        _ => {
2907            return VerifyResult::fail(format!(
2908                "q^k exceeds enum guard {MAX_ENUM}; distance not exhaustively verifiable — refusing to claim"
2909            ));
2910        }
2911    }
2912    let qk = qk.unwrap();
2913    let mut dmin = n + 1;
2914    // Enumerate all nonzero message vectors msg in GF(q)^k.
2915    let mut msg = vec![0u64; k];
2916    for code in 1..qk {
2917        // decode `code` as a base-q digit vector
2918        let mut x = code;
2919        for m in msg.iter_mut() {
2920            *m = x % q;
2921            x /= q;
2922        }
2923        let mut weight = 0usize;
2924        for c in 0..n {
2925            let mut s = 0u64;
2926            for i in 0..k {
2927                if msg[i] != 0 {
2928                    s = (s + msg[i] * g[i][c]) % q;
2929                }
2930            }
2931            if s != 0 {
2932                weight += 1;
2933            }
2934        }
2935        if weight < dmin {
2936            dmin = weight;
2937        }
2938    }
2939    let ok = dmin >= claimed_d;
2940    let rel = if ok { ">=" } else { "<" };
2941    VerifyResult {
2942        ok,
2943        message: format!(
2944            "[{n},{k},{dmin}]_{q} verified (min weight {dmin} {rel} claimed {claimed_d})"
2945        ),
2946        value: Some(dmin as f64),
2947    }
2948}
2949
2950// --- small numeric / combinatorial helpers -------------------------------
2951
2952/// Advance an index tuple to the next combination-with-replacement over
2953/// `[0, m)`. Returns false when exhausted.
2954fn advance_with_replacement(idx: &mut [usize], m: usize) -> bool {
2955    let h = idx.len();
2956    let mut i = h;
2957    loop {
2958        if i == 0 {
2959            return false;
2960        }
2961        i -= 1;
2962        if idx[i] != m - 1 {
2963            let nv = idx[i] + 1;
2964            for slot in idx.iter_mut().take(h).skip(i) {
2965                *slot = nv;
2966            }
2967            return true;
2968        }
2969    }
2970}
2971
2972/// Visit every strictly-increasing `t`-combination of indices in
2973/// `[0, n)`.
2974fn each_combination(n: usize, t: usize, f: &mut impl FnMut(&[usize])) {
2975    if t > n {
2976        return;
2977    }
2978    let mut idx: Vec<usize> = (0..t).collect();
2979    loop {
2980        f(&idx);
2981        // advance
2982        let mut i = t;
2983        loop {
2984            if i == 0 {
2985                return;
2986            }
2987            i -= 1;
2988            if idx[i] != i + n - t {
2989                idx[i] += 1;
2990                for j in (i + 1)..t {
2991                    idx[j] = idx[j - 1] + 1;
2992                }
2993                break;
2994            }
2995        }
2996    }
2997}
2998
2999fn is_prime(q: u64) -> bool {
3000    if q < 2 {
3001        return false;
3002    }
3003    let mut p = 2u64;
3004    while p * p <= q {
3005        if q.is_multiple_of(p) {
3006            return false;
3007        }
3008        p += 1;
3009    }
3010    true
3011}
3012
3013/// Rank over `GF(q)` (q prime) of an integer matrix (entries already
3014/// reduced mod q).
3015// Gaussian elimination over GF(q): the inner loops index two rows by the same
3016// column, so a range loop is the honest form (iterator pairs would obscure it).
3017#[allow(clippy::needless_range_loop)]
3018fn gf_rank(rows: &[Vec<u64>], q: u64) -> usize {
3019    let mut m: Vec<Vec<u64>> = rows.to_vec();
3020    if m.is_empty() {
3021        return 0;
3022    }
3023    let ncols = m[0].len();
3024    let mut rank = 0usize;
3025    for col in 0..ncols {
3026        let piv = (rank..m.len()).find(|&r| !m[r][col].is_multiple_of(q));
3027        let Some(piv) = piv else { continue };
3028        m.swap(rank, piv);
3029        let inv = mod_inv(m[rank][col] % q, q);
3030        for c in 0..ncols {
3031            m[rank][c] = (m[rank][c] * inv) % q;
3032        }
3033        for r in 0..m.len() {
3034            if r != rank && !m[r][col].is_multiple_of(q) {
3035                let f = m[r][col] % q;
3036                for c in 0..ncols {
3037                    m[r][c] = (m[r][c] + q - (f * m[rank][c]) % q) % q;
3038                }
3039            }
3040        }
3041        rank += 1;
3042        if rank == m.len() {
3043            break;
3044        }
3045    }
3046    rank
3047}
3048
3049/// Modular inverse of `a` mod prime `q` via Fermat's little theorem.
3050fn mod_inv(a: u64, q: u64) -> u64 {
3051    mod_pow(a, q - 2, q)
3052}
3053
3054fn mod_pow(mut base: u64, mut exp: u64, modulus: u64) -> u64 {
3055    let mut result = 1u64;
3056    base %= modulus;
3057    while exp > 0 {
3058        if exp & 1 == 1 {
3059            result = (result * base) % modulus;
3060        }
3061        exp >>= 1;
3062        base = (base * base) % modulus;
3063    }
3064    result
3065}
3066
3067#[cfg(test)]
3068mod tests {
3069    use super::*;
3070
3071    // A genuine a(8) >= 33 Sidon witness fragment is large; use a small
3072    // hand-checked Sidon set for the unit test, plus corrupt-it checks.
3073    fn small_sidon() -> Vec<Vec<i64>> {
3074        // In {0,1}^3: {000, 100, 010, 001} — pairwise sums all distinct?
3075        // sums include 000,100,010,001 (i=j) and 110,101,011 (i<j) — all
3076        // distinct. A valid (small) Sidon set.
3077        vec![vec![0, 0, 0], vec![1, 0, 0], vec![0, 1, 0], vec![0, 0, 1]]
3078    }
3079
3080    // ---- claim<->witness faithfulness (the un-forgeable exact-lane core) ----
3081
3082    #[test]
3083    fn faithful_parses_real_a309370_assertion() {
3084        let text = "OEIS A309370 a(20) >= 1989: a Sidon set of 1989 distinct binary \
3085                    vectors in {0,1}^20 under componentwise integer addition, with all \
3086                    pairwise sums distinct. Frozen-verified by vela-verify (sidon kind).";
3087        let p = parse_claim(text).expect("should parse the canonical A309370 form");
3088        assert_eq!(p.kind, "sidon");
3089        assert_eq!(p.ambient_n, Some(20));
3090        assert_eq!(p.bound, 1989);
3091        assert!(!p.exact);
3092    }
3093
3094    #[test]
3095    fn faithful_happy_path() {
3096        let text = "a(3) >= 4: a Sidon set of 4 vectors in {0,1}^3.";
3097        let w = Witness::Sidon {
3098            n: 3,
3099            points: small_sidon(),
3100            claimed_size: Some(4),
3101        };
3102        let f = claim_witness_faithful(text, &w);
3103        assert!(f.faithful, "{:?}", f.reasons);
3104    }
3105
3106    // ATTACK: inflated assertion over a valid-but-weaker witness. verify_witness
3107    // passes (it IS a genuine size-4 Sidon set), but the claim says >= 5.
3108    #[test]
3109    fn faithful_rejects_inflated_lower_bound() {
3110        let text = "a(3) >= 5: a Sidon set of 5 vectors in {0,1}^3.";
3111        let w = Witness::Sidon {
3112            n: 3,
3113            points: small_sidon(), // only 4 points
3114            claimed_size: None,
3115        };
3116        assert!(verify_witness(&w).ok, "the witness itself is valid");
3117        let f = claim_witness_faithful(text, &w);
3118        assert!(!f.faithful);
3119        assert!(f.reasons.iter().any(|r| r.contains("does not establish")));
3120    }
3121
3122    // ATTACK: claim names a different ambient dimension than the witness.
3123    #[test]
3124    fn faithful_rejects_dimension_mismatch() {
3125        let text = "a(8) >= 4: a Sidon set of 4 vectors in {0,1}^8.";
3126        let w = Witness::Sidon {
3127            n: 3,
3128            points: small_sidon(),
3129            claimed_size: None,
3130        };
3131        let f = claim_witness_faithful(text, &w);
3132        assert!(!f.faithful);
3133        assert!(f.reasons.iter().any(|r| r.contains("dimension")));
3134    }
3135
3136    // ATTACK: a Golomb claim bound to a Sidon witness.
3137    #[test]
3138    fn faithful_rejects_kind_mismatch() {
3139        let text = "an optimal Golomb ruler of order 4 with >= 4 marks.";
3140        let w = Witness::Sidon {
3141            n: 3,
3142            points: small_sidon(),
3143            claimed_size: None,
3144        };
3145        let f = claim_witness_faithful(text, &w);
3146        assert!(!f.faithful);
3147        assert!(f.reasons.iter().any(|r| r.contains("kind")));
3148    }
3149
3150    // ATTACK: a witness that does not actually verify (collision injected).
3151    #[test]
3152    fn faithful_rejects_invalid_witness() {
3153        let text = "a(3) >= 4: a Sidon set of 4 vectors in {0,1}^3.";
3154        // {000, 100, 100, 010}: 100 repeated -> not a valid Sidon set.
3155        let w = Witness::Sidon {
3156            n: 3,
3157            points: vec![vec![0, 0, 0], vec![1, 0, 0], vec![1, 0, 0], vec![0, 1, 0]],
3158            claimed_size: None,
3159        };
3160        let f = claim_witness_faithful(text, &w);
3161        assert!(!f.faithful);
3162        assert!(f.reasons.iter().any(|r| r.contains("does not verify")));
3163    }
3164
3165    // ATTACK: an existence/asymptotic assertion with no exact bound -> the
3166    // conservative parser refuses, so it can never auto-admit.
3167    #[test]
3168    fn faithful_refuses_unparseable_asymptotic_claim() {
3169        let text = "Singer's perfect-difference-set construction yields Sidon sets in \
3170                    {1,...,N} of size sqrt(N) + O(N^{1/4}).";
3171        let w = Witness::Sidon {
3172            n: 3,
3173            points: small_sidon(),
3174            claimed_size: None,
3175        };
3176        let f = claim_witness_faithful(text, &w);
3177        assert!(!f.faithful);
3178        assert!(f.parsed.is_none());
3179    }
3180
3181    // ATTACK: ambiguous claim carrying BOTH a lower bound and an equality.
3182    #[test]
3183    fn faithful_refuses_ambiguous_bound() {
3184        let text = "a Sidon set in {0,1}^3 with >= 4 and exactly 5 elements.";
3185        assert!(parse_claim(text).is_none());
3186    }
3187
3188    #[test]
3189    fn faithful_routes_equality_optimality_to_review() {
3190        // An equality / optimality claim (`= N` / `exactly N`) asserts the
3191        // MAXIMUM is N (no larger object exists), which a single construction
3192        // witness cannot prove — it establishes only a lower bound. So even a
3193        // size-matching witness must NOT auto-admit an `exactly` claim; it
3194        // routes to review. (Closes the inflation-via-equality vector: an agent
3195        // cannot turn a real `a(n) >= k` witness into an `a(n) = k`/headline
3196        // claim the floor never verified.)
3197        let w = Witness::Sidon {
3198            n: 3,
3199            points: small_sidon(), // 4 points
3200            claimed_size: None,
3201        };
3202        let f = claim_witness_faithful("a Sidon set in {0,1}^3 with exactly 4 elements.", &w);
3203        assert!(
3204            !f.faithful,
3205            "equality/optimality is not witness-establishable"
3206        );
3207        assert!(f.reasons.iter().any(|r| r.contains("equality/optimality")));
3208        // a standalone `= N` headline is treated the same way.
3209        let f2 = claim_witness_faithful("Sidon a(3) = 4 in {0,1}^3 (new record).", &w);
3210        assert!(!f2.faithful, "a `= N` headline also routes to review");
3211    }
3212
3213    // ---- second-adversarial-review regressions (floor as the sole gate) ----
3214
3215    // ATTACK (inflated-claim / witness-substitution): a genuine small witness
3216    // dressed with an `a(20)` headline. Reading the a(N) order and binding it to
3217    // the witness n closes both the omit-dimension and the easy-witness-for-
3218    // hard-claim bypass.
3219    #[test]
3220    fn faithful_binds_a_of_n_order_to_witness() {
3221        let w = Witness::Sidon {
3222            n: 3,
3223            points: small_sidon(),
3224            claimed_size: None,
3225        }; // a valid 4-point Sidon set in {0,1}^3
3226        assert!(verify_witness(&w).ok, "the witness itself is valid");
3227        // a(20) order vs witness n=3 -> mismatch, even though size 4 >= 4.
3228        let f = claim_witness_faithful("Sidon record a(20): at least 4 points.", &w);
3229        assert!(
3230            !f.faithful,
3231            "an a(20) claim cannot ride an n=3 witness: {:?}",
3232            f.reasons
3233        );
3234        // No ambient/order at all -> mandatory-dimension fail closed.
3235        let f2 = claim_witness_faithful("A Sidon set, at least 4 points, beats the record.", &w);
3236        assert!(
3237            !f2.faithful,
3238            "a dimensioned claim with no ambient routes to review: {:?}",
3239            f2.reasons
3240        );
3241    }
3242
3243    // ATTACK (dual-bound headline): a `= 2500` headline beside an `at least 4`
3244    // clause. The lower bound co-occurring with an equality marker is ambiguous.
3245    #[test]
3246    fn faithful_rejects_dual_bound_headline() {
3247        let w = Witness::Sidon {
3248            n: 3,
3249            points: small_sidon(),
3250            claimed_size: None,
3251        };
3252        let f = claim_witness_faithful(
3253            "Sidon in {0,1}^3: a(3) = 2500 (beats prior 1989). The witness has at least 4 points.",
3254            &w,
3255        );
3256        assert!(
3257            !f.faithful,
3258            "a `= headline` beside an `at least` clause is ambiguous: {:?}",
3259            f.reasons
3260        );
3261        assert!(
3262            f.parsed.is_none(),
3263            "the dual lower+equality marker fails parse"
3264        );
3265    }
3266
3267    // ATTACK (reproduce-spoof / GF(2) dimension): a GF(2)^5 witness cannot
3268    // establish an a(4) claim, because element 16 sits outside GF(2)^4.
3269    #[test]
3270    fn faithful_gf2_binds_dimension() {
3271        let good = Witness::Gf2Sidon {
3272            elements: vec![1, 2, 4],
3273            claimed_size: None,
3274        };
3275        assert!(verify_witness(&good).ok);
3276        let f = claim_witness_faithful("OEIS A394031 a(3) >= 3: a Sidon set in GF(2)^3.", &good);
3277        assert!(f.faithful, "genuine GF(2)^3 claim: {:?}", f.reasons);
3278
3279        let wide = Witness::Gf2Sidon {
3280            elements: vec![1, 2, 4, 8, 16],
3281            claimed_size: None,
3282        };
3283        assert!(
3284            verify_witness(&wide).ok,
3285            "the wider witness is itself valid"
3286        );
3287        let f2 = claim_witness_faithful("OEIS A394031 a(4) >= 5: a Sidon set in GF(2)^4.", &wide);
3288        assert!(
3289            !f2.faithful,
3290            "an element outside GF(2)^4 must fail: {:?}",
3291            f2.reasons
3292        );
3293        // dimension omitted -> mandatory fail closed.
3294        let f3 = claim_witness_faithful("A GF(2) Sidon set, at least 5 elements.", &wide);
3295        assert!(!f3.faithful, "{:?}", f3.reasons);
3296    }
3297
3298    // B_h and constant-weight bind their extra hardness parameter (h; d,w).
3299    // The round-3 attack (an EASY witness dressed with a HARD headline) now
3300    // FAILS on the parameter mismatch; a matched claim PASSES; an unstated
3301    // parameter routes to review.
3302    #[test]
3303    fn faithful_binds_bh_order_and_constant_weight_params() {
3304        // B_h: the witness is a valid B_2 set.
3305        let bh = Witness::Bh {
3306            n: 3,
3307            h: 2,
3308            points: small_sidon(),
3309            claimed_size: None,
3310        };
3311        assert!(verify_witness(&bh).ok, "the B_2 witness is itself valid");
3312        // ATTACK: a B_3 headline over a B_2 witness -> h mismatch -> rejected.
3313        let attack = claim_witness_faithful("a B_3 set in {0,1}^3: a(3) >= 4.", &bh);
3314        assert!(
3315            !attack.faithful,
3316            "B_3 claim cannot ride a B_2 witness: {:?}",
3317            attack.reasons
3318        );
3319        assert!(attack.reasons.iter().any(|r| r.contains("does not match")));
3320        // GENUINE: a matched B_2 claim is faithful.
3321        let ok = claim_witness_faithful("a B_2 set in {0,1}^3: a(3) >= 4.", &bh);
3322        assert!(ok.faithful, "matched B_2 claim: {:?}", ok.reasons);
3323        // h unstated -> route to review.
3324        let bare = claim_witness_faithful("a bh set in {0,1}^3: a(3) >= 4.", &bh);
3325        assert!(
3326            !bare.faithful,
3327            "unstated h routes to review: {:?}",
3328            bare.reasons
3329        );
3330
3331        // constant-weight: the witness is a valid A(4,2,1) code (2 weight-1 words).
3332        let cw = Witness::ConstantWeight {
3333            n: 4,
3334            d: 2,
3335            w: 1,
3336            words: vec![vec![1, 0, 0, 0], vec![0, 1, 0, 0]],
3337            claimed_size: None,
3338        };
3339        assert!(
3340            verify_witness(&cw).ok,
3341            "the A(4,2,1) witness is itself valid"
3342        );
3343        // ATTACK: a hard A(4,10,8) headline over the trivial witness -> rejected.
3344        let attack2 = claim_witness_faithful("constant weight code A(4,10,8) >= 2.", &cw);
3345        assert!(
3346            !attack2.faithful,
3347            "A(4,10,8) claim cannot ride an A(4,2,1) witness: {:?}",
3348            attack2.reasons
3349        );
3350        assert!(attack2.reasons.iter().any(|r| r.contains("does not match")));
3351        // GENUINE: the matched A(4,2,1) claim is faithful.
3352        let ok2 = claim_witness_faithful("constant weight code A(4,2,1) >= 2.", &cw);
3353        assert!(ok2.faithful, "matched A(4,2,1) claim: {:?}", ok2.reasons);
3354        // (d,w) unstated -> route to review.
3355        let bare2 = claim_witness_faithful("a constant weight code, a(4) >= 2.", &cw);
3356        assert!(
3357            !bare2.faithful,
3358            "unstated (d,w) routes to review: {:?}",
3359            bare2.reasons
3360        );
3361    }
3362
3363    // The canonical, witness-derived verified claim (residual #1): the displayed
3364    // claim is DERIVED from the witness, so prose cannot puff a true bound.
3365    #[test]
3366    fn canonical_claim_is_witness_derived() {
3367        let s = Witness::Sidon {
3368            n: 3,
3369            points: small_sidon(),
3370            claimed_size: None,
3371        };
3372        let c = canonical_claim(&s).expect("sidon has a canonical claim");
3373        assert!(c.contains("a(3) >= 4"), "{c}");
3374        // GF(2): n is the widest element's bit width (here 4 -> bit index 2).
3375        let g = Witness::Gf2Sidon {
3376            elements: vec![1, 2, 4],
3377            claimed_size: None,
3378        };
3379        let cg = canonical_claim(&g).expect("gf2 has a canonical claim");
3380        assert!(cg.contains("a(3) >= 3"), "{cg}");
3381        // golomb (not floor-admissible) has no canonical claim.
3382        assert!(
3383            canonical_claim(&Witness::Golomb {
3384                marks: vec![0, 1, 3]
3385            })
3386            .is_none()
3387        );
3388    }
3389
3390    // Golomb has no sound witness->lower-bound binding defined: route to review.
3391    #[test]
3392    fn faithful_golomb_routes_to_review() {
3393        let w = Witness::Golomb {
3394            marks: vec![0, 1, 3],
3395        };
3396        assert!(verify_witness(&w).ok);
3397        let f = claim_witness_faithful("Golomb ruler a(3) >= 3.", &w);
3398        assert!(
3399            !f.faithful,
3400            "golomb is not floor-admissible: {:?}",
3401            f.reasons
3402        );
3403    }
3404
3405    // ---- difference triangle set (HorizonMath (7,5), scope < 112) ----
3406
3407    #[test]
3408    fn diff_triangle_accepts_valid_and_reports_scope() {
3409        // rows {0,1,3} (diffs 1,2,3) and {0,4,9} (diffs 4,5,9): all distinct.
3410        let w = Witness::DiffTriangle {
3411            rows: vec![vec![0, 1, 3], vec![0, 4, 9]],
3412            claimed_scope: Some(9),
3413        };
3414        let r = verify_witness(&w);
3415        assert!(r.ok, "{}", r.message);
3416        assert!(r.message.contains("scope 9"));
3417    }
3418
3419    #[test]
3420    fn diff_triangle_rejects_global_difference_collision() {
3421        // row2 {0,2,5} has differences 2 and 3, which collide with row1.
3422        let w = Witness::DiffTriangle {
3423            rows: vec![vec![0, 1, 3], vec![0, 2, 5]],
3424            claimed_scope: None,
3425        };
3426        let r = verify_witness(&w);
3427        assert!(!r.ok);
3428        assert!(r.message.contains("repeats"));
3429    }
3430
3431    #[test]
3432    fn diff_triangle_rejects_non_increasing_and_nonzero_start() {
3433        assert!(!verify_diff_triangle(&[vec![0, 3, 1]], None).ok);
3434        assert!(!verify_diff_triangle(&[vec![1, 2, 4]], None).ok);
3435    }
3436
3437    #[test]
3438    fn diff_triangle_rejects_inflated_scope_claim() {
3439        // A valid set, but a record claim ("scope below 112") that lies about
3440        // the actual scope must fail.
3441        let w = Witness::DiffTriangle {
3442            rows: vec![vec![0, 1, 3], vec![0, 4, 9]],
3443            claimed_scope: Some(100),
3444        };
3445        assert!(!verify_witness(&w).ok);
3446    }
3447
3448    #[test]
3449    fn gf2_sidon_accepts_distinct_xors_and_rejects_collision() {
3450        // {0,1,2}: XORs 1,2,3 all distinct -> GF(2) Sidon.
3451        let ok = Witness::Gf2Sidon {
3452            elements: vec![0, 1, 2],
3453            claimed_size: Some(3),
3454        };
3455        assert!(verify_witness(&ok).ok);
3456        // {0,1,2,3}: 0^3 = 3 and 1^2 = 3 collide -> not Sidon.
3457        let bad = Witness::Gf2Sidon {
3458            elements: vec![0, 1, 2, 3],
3459            claimed_size: None,
3460        };
3461        assert!(!verify_witness(&bad).ok);
3462        // duplicate element rejected.
3463        let dup = Witness::Gf2Sidon {
3464            elements: vec![5, 5],
3465            claimed_size: None,
3466        };
3467        assert!(!verify_witness(&dup).ok);
3468    }
3469
3470    #[test]
3471    fn union_free_accepts_and_rejects_union_member() {
3472        // {1,2},{1,3},{2,3}: no member is a union of others over {1,2,3}.
3473        let ok = Witness::UnionFree {
3474            n: 3,
3475            sets: vec![vec![1, 2], vec![1, 3], vec![2, 3]],
3476            claimed_size: Some(3),
3477        };
3478        assert!(verify_witness(&ok).ok);
3479        // {1},{2},{1,2}: {1,2} = {1} ∪ {2} -> not union-free.
3480        let bad = Witness::UnionFree {
3481            n: 2,
3482            sets: vec![vec![1], vec![2], vec![1, 2]],
3483            claimed_size: None,
3484        };
3485        assert!(!verify_witness(&bad).ok);
3486    }
3487
3488    #[test]
3489    fn rook_directions_counts_classes_and_checks_claim() {
3490        // n=2, perm [1,2]: one pair, one direction class (1,1). a(2)=1.
3491        let ok = Witness::RookDirections {
3492            n: 2,
3493            perm: vec![1, 2],
3494            claimed_directions: Some(1),
3495        };
3496        assert!(verify_witness(&ok).ok);
3497        // wrong claimed count rejected.
3498        let bad = Witness::RookDirections {
3499            n: 2,
3500            perm: vec![1, 2],
3501            claimed_directions: Some(2),
3502        };
3503        assert!(!verify_witness(&bad).ok);
3504        // repeated column (attacking rooks) rejected.
3505        let attack = Witness::RookDirections {
3506            n: 2,
3507            perm: vec![1, 1],
3508            claimed_directions: None,
3509        };
3510        assert!(!verify_witness(&attack).ok);
3511    }
3512
3513    #[test]
3514    fn unsat_cert_accepts_rup_proofs_and_rejects_corruption() {
3515        // (x) ∧ (¬x): the empty clause is RUP from clauses 1, 2.
3516        let w = Witness::UnsatCert {
3517            cnf: vec![vec![1], vec![-1]],
3518            proof: vec![LratStep {
3519                id: 3,
3520                literals: vec![],
3521                hints: vec![1, 2],
3522                rat_hints: vec![],
3523            }],
3524        };
3525        assert!(verify_witness(&w).ok);
3526        // (a) ∧ (b) ∧ (¬a ∨ ¬b): empty clause RUP from 1, 2, 3.
3527        let w2 = Witness::UnsatCert {
3528            cnf: vec![vec![1], vec![2], vec![-1, -2]],
3529            proof: vec![LratStep {
3530                id: 4,
3531                literals: vec![],
3532                hints: vec![1, 2, 3],
3533                rat_hints: vec![],
3534            }],
3535        };
3536        assert!(verify_witness(&w2).ok);
3537        // Drop the conflict-producing antecedent → no conflict → rejected.
3538        let bad = Witness::UnsatCert {
3539            cnf: vec![vec![1], vec![2], vec![-1, -2]],
3540            proof: vec![LratStep {
3541                id: 4,
3542                literals: vec![],
3543                hints: vec![1, 2],
3544                rat_hints: vec![],
3545            }],
3546        };
3547        assert!(!verify_witness(&bad).ok);
3548        // A satisfiable CNF cannot derive the empty clause with any RUP step.
3549        let sat = Witness::UnsatCert {
3550            cnf: vec![vec![1, 2]],
3551            proof: vec![LratStep {
3552                id: 2,
3553                literals: vec![],
3554                hints: vec![1],
3555                rat_hints: vec![],
3556            }],
3557        };
3558        assert!(!verify_witness(&sat).ok);
3559    }
3560
3561    #[test]
3562    fn crt_partial_cover_accepts_real_rows_and_rejects_corruption() {
3563        let m = "8168305011630835886634520238999";
3564        let rows = vec![
3565            CrtCoverRow {
3566                p: 5,
3567                ord2: 4,
3568                ord3: 4,
3569                h: 4,
3570                t_p: 1,
3571                m_mod_p: 4,
3572                line: [1, 3, 0, 4],
3573            },
3574            CrtCoverRow {
3575                p: 7,
3576                ord2: 3,
3577                ord3: 6,
3578                h: 6,
3579                t_p: 1,
3580                m_mod_p: 6,
3581                line: [2, 1, 0, 6],
3582            },
3583        ];
3584        assert!(verify_crt_partial_cover(m, &rows).ok);
3585        // Corrupt t_p.
3586        let mut bad = rows.clone();
3587        bad[0].t_p = 2;
3588        assert!(!verify_crt_partial_cover(m, &bad).ok);
3589        // Corrupt the affine line.
3590        let mut bad = rows.clone();
3591        bad[1].line = [2, 1, 1, 6];
3592        assert!(!verify_crt_partial_cover(m, &bad).ok);
3593        // m divisible by 3 is rejected.
3594        assert!(!verify_crt_partial_cover("9", &rows).ok);
3595    }
3596
3597    #[test]
3598    fn kummer_no_carry_accepts_erdos684_table_and_rejects_corruption() {
3599        let entries = vec![
3600            KummerEntry { k: 3, m: 36 },
3601            KummerEntry { k: 7, m: 88200 },
3602            KummerEntry { k: 12, m: 64033200 },
3603        ];
3604        assert!(verify_kummer_no_carry(&entries).ok);
3605        // Wrong M_k.
3606        let bad = vec![KummerEntry { k: 3, m: 72 }];
3607        assert!(!verify_kummer_no_carry(&bad).ok);
3608        // Out of guard range.
3609        assert!(!verify_kummer_no_carry(&[KummerEntry { k: 25, m: 1 }]).ok);
3610    }
3611
3612    #[test]
3613    fn min_binom_gcd_accepts_erdos700_cases_and_rejects_corruption() {
3614        let cases = vec![
3615            MinGcdCase { n: 30, f: 6 },
3616            MinGcdCase { n: 77, f: 7 },
3617            MinGcdCase { n: 49, f: 7 },
3618        ];
3619        assert!(verify_min_binom_gcd(&cases).ok);
3620        assert!(!verify_min_binom_gcd(&[MinGcdCase { n: 30, f: 5 }]).ok);
3621    }
3622
3623    #[test]
3624    fn binom_deficiency_accepts_els93_row_and_rejects_corruption() {
3625        // ELS93 table row k=8, N=44: delta=2 at slots [4, 6].
3626        let good = DeficiencyEntry {
3627            k: 8,
3628            n: "44".to_string(),
3629            delta: 2,
3630            slots: Some(vec![4, 6]),
3631        };
3632        assert!(verify_binom_deficiency(&[good.clone()]).ok);
3633        // Count-only form.
3634        let count_only = DeficiencyEntry {
3635            slots: None,
3636            ..good.clone()
3637        };
3638        assert!(verify_binom_deficiency(&[count_only]).ok);
3639        // Wrong delta.
3640        let bad = DeficiencyEntry {
3641            delta: 1,
3642            slots: None,
3643            ..good.clone()
3644        };
3645        assert!(!verify_binom_deficiency(&[bad]).ok);
3646        // Wrong slots.
3647        let bad = DeficiencyEntry {
3648            slots: Some(vec![4, 7]),
3649            ..good
3650        };
3651        assert!(!verify_binom_deficiency(&[bad]).ok);
3652        // A big-N entry (the k=129 delta=1 example) exercises the u128 path.
3653        let big = DeficiencyEntry {
3654            k: 129,
3655            n: "3180883073384828665489".to_string(),
3656            delta: 1,
3657            slots: Some(vec![65]),
3658        };
3659        assert!(verify_binom_deficiency(&[big]).ok);
3660    }
3661
3662    #[test]
3663    fn binom_exception_enum_matches_els_for_small_k_and_rejects_corruption() {
3664        // Re-derived ELS exceptions with k <= 8 (49 candidates).
3665        let els8: Vec<(u64, u64)> = vec![(7, 3), (13, 4), (14, 4), (23, 5), (62, 6), (44, 8)];
3666        assert!(verify_binom_exception_enum(8, &els8).ok);
3667        // Missing one exception fails.
3668        assert!(!verify_binom_exception_enum(8, &els8[1..]).ok);
3669        // A fabricated extra exception fails.
3670        let mut padded = els8.clone();
3671        padded.push((100, 5));
3672        assert!(!verify_binom_exception_enum(8, &padded).ok);
3673    }
3674
3675    #[test]
3676    fn interval_product_accepts_erdos1056_example_and_rejects_corruption() {
3677        // erdosproblems.com/1056 example: p=11, cuts [2,4,7].
3678        // (3·4)=12≡1, (5·6·7)=210≡1 (mod 11).
3679        assert!(verify_interval_product(11, &[2, 4, 7]).ok);
3680        // A non-prime modulus is rejected.
3681        assert!(!verify_interval_product(12, &[2, 4, 7]).ok);
3682        // Perturb a cut so an interval product is no longer 1 mod p.
3683        assert!(!verify_interval_product(11, &[2, 4, 8]).ok);
3684        // Non-increasing cuts are rejected.
3685        assert!(!verify_interval_product(11, &[4, 4, 7]).ok);
3686    }
3687
3688    #[test]
3689    fn sidon_accepts_valid_and_rejects_corrupted() {
3690        assert!(verify_sidon(&small_sidon(), 3).ok);
3691        // Corrupt: add a 4th point that creates a sum collision.
3692        // 110 + 000 = 110 and 100 + 010 = 110 -> collision.
3693        let mut bad = small_sidon();
3694        bad.push(vec![1, 1, 0]);
3695        assert!(!verify_sidon(&bad, 3).ok, "corrupted Sidon must fail");
3696    }
3697
3698    #[test]
3699    fn packed_binary_sidon_path_matches_coordinate_semantics() {
3700        let good = small_sidon();
3701        let result = verify_sidon(&good, 3);
3702        assert!(result.ok, "{}", result.message);
3703        assert!(result.message.contains("10 pairwise sums"));
3704
3705        let collision = vec![vec![0, 0, 0], vec![1, 0, 0], vec![0, 1, 0], vec![1, 1, 0]];
3706        assert!(!verify_sidon(&collision, 3).ok);
3707    }
3708
3709    #[test]
3710    fn sidon_rejects_non_binary_and_dups() {
3711        assert!(!verify_sidon(&[vec![0, 2, 0]], 3).ok);
3712        assert!(!verify_sidon(&[vec![1, 0, 0], vec![1, 0, 0]], 3).ok);
3713    }
3714
3715    #[test]
3716    fn claimed_size_mismatch_fails() {
3717        let w = Witness::Sidon {
3718            n: 3,
3719            points: small_sidon(),
3720            claimed_size: Some(99),
3721        };
3722        let r = verify_witness(&w);
3723        assert!(!r.ok, "claimed_size 99 != actual 4 must fail");
3724        assert!(r.message.contains("claimed_size"));
3725    }
3726
3727    #[test]
3728    fn golomb_accepts_valid_and_rejects_corrupted() {
3729        // {0,1,4,6} is a perfect Golomb ruler (differences 1,4,6,3,5,2).
3730        assert!(verify_golomb(&[0, 1, 4, 6]).ok);
3731        // {0,1,2,4}: differences 1,2,4,1,... -> repeat -> fail.
3732        assert!(!verify_golomb(&[0, 1, 2, 4]).ok);
3733    }
3734
3735    #[test]
3736    fn cap_accepts_valid_and_rejects_collinear() {
3737        // {0,1} along one axis in F_3^1 is a cap (need 3 for a line).
3738        assert!(verify_cap(&[vec![0], vec![1]], 1).ok);
3739        // {0,1,2} in F_3^1: 0+1+2 = 0 mod 3 -> collinear -> fail.
3740        assert!(!verify_cap(&[vec![0], vec![1], vec![2]], 1).ok);
3741    }
3742
3743    #[test]
3744    fn bh_h2_matches_sidon() {
3745        assert!(verify_bh(&small_sidon(), 3, 2).ok);
3746        let mut bad = small_sidon();
3747        bad.push(vec![1, 1, 0]);
3748        assert!(!verify_bh(&bad, 3, 2).ok);
3749    }
3750
3751    #[test]
3752    fn covering_accepts_full_and_rejects_gap() {
3753        // C(4,3,2): blocks {0,1,2},{0,1,3},{0,2,3},{1,2,3} cover every pair.
3754        let full = vec![vec![0, 1, 2], vec![0, 1, 3], vec![0, 2, 3], vec![1, 2, 3]];
3755        assert!(verify_covering(&full, 4, 3, 2).ok);
3756        // Drop a block: pair {2,3} only in {0,2,3} and {1,2,3}; remove both.
3757        let gap = vec![vec![0, 1, 2], vec![0, 1, 3]];
3758        assert!(!verify_covering(&gap, 4, 3, 2).ok);
3759    }
3760
3761    #[test]
3762    fn constant_weight_checks_weight_and_distance() {
3763        // A(4,2,2): {1100, 0011} weight 2, distance 4 >= 2.
3764        let ok = vec![vec![1, 1, 0, 0], vec![0, 0, 1, 1]];
3765        assert!(verify_constant_weight(&ok, 4, 2, 2).ok);
3766        // wrong weight
3767        assert!(!verify_constant_weight(&[vec![1, 1, 1, 0]], 4, 2, 2).ok);
3768    }
3769
3770    #[test]
3771    fn costas_accepts_valid_and_rejects_nonpermutation() {
3772        // {0,2,3,1} is a Costas array of order 4.
3773        assert!(verify_costas(&[0, 2, 3, 1]).ok);
3774        assert!(!verify_costas(&[0, 0, 1, 2]).ok);
3775    }
3776
3777    #[test]
3778    fn linear_code_verifies_distance_and_refuses_nonprime() {
3779        // [3,1,3]_2 repetition code: generator [1,1,1], min weight 3.
3780        let g = vec![vec![1, 1, 1]];
3781        let r = verify_linear_code(&g, 2, 3);
3782        assert!(r.ok, "{}", r.message);
3783        // claim d=4 on a min-weight-3 code must fail.
3784        assert!(!verify_linear_code(&g, 2, 4).ok);
3785        // non-prime q refused.
3786        assert!(!verify_linear_code(&g, 4, 1).ok);
3787    }
3788
3789    #[test]
3790    fn witness_serde_round_trip() {
3791        let w = Witness::Sidon {
3792            n: 3,
3793            points: small_sidon(),
3794            claimed_size: Some(4),
3795        };
3796        let json = serde_json::to_string(&w).unwrap();
3797        assert!(json.contains("\"kind\":\"sidon\""));
3798        let back: Witness = serde_json::from_str(&json).unwrap();
3799        assert_eq!(back, w);
3800        assert!(verify_witness(&back).ok);
3801    }
3802}
3803
3804#[cfg(test)]
3805mod balanced_coloring_tests {
3806    use super::*;
3807    use std::collections::BTreeMap;
3808
3809    fn pentagon_k5() -> BTreeMap<String, u32> {
3810        let pent = [(0, 1), (1, 2), (2, 3), (3, 4), (0, 4)];
3811        let mut ec = BTreeMap::new();
3812        for i in 0..5usize {
3813            for j in (i + 1)..5 {
3814                let c = if pent.contains(&(i, j)) { 1 } else { 2 };
3815                ec.insert(format!("{i},{j}"), c);
3816            }
3817        }
3818        ec
3819    }
3820
3821    #[test]
3822    fn pentagon_coloring_is_balanced() {
3823        let r = verify_balanced_coloring(5, 2, &pentagon_k5());
3824        assert!(r.ok, "{}", r.message);
3825    }
3826
3827    #[test]
3828    fn flipped_edge_breaks_balance() {
3829        let mut ec = pentagon_k5();
3830        ec.insert("0,1".to_string(), 2);
3831        let r = verify_balanced_coloring(5, 2, &ec);
3832        assert!(!r.ok);
3833    }
3834
3835    #[test]
3836    fn dominates_orders_by_n_at_same_r() {
3837        let w5 = Witness::BalancedColoring {
3838            n: 5,
3839            r: 2,
3840            edge_colors: pentagon_k5(),
3841        };
3842        let w4 = Witness::BalancedColoring {
3843            n: 4,
3844            r: 2,
3845            edge_colors: BTreeMap::new(),
3846        };
3847        assert_eq!(dominates(&w5, &w4), Ok(true));
3848        assert_eq!(dominates(&w4, &w5), Ok(false));
3849    }
3850}
3851
3852#[cfg(test)]
3853mod rat_tests {
3854    use super::*;
3855
3856    /// cnf: (1 2)(-1 3)(2)(-2) — UNSAT via the unit pair. Step 5 adds
3857    /// the blocked clause (-1 -2): NOT RUP (clause (2) is satisfied
3858    /// under the falsifying assignment, blocking propagation) but RAT
3859    /// on pivot -1 — the only clause containing 1 is (1 2), whose
3860    /// resolvent {-1,-2,2} is tautological. Step 6 derives empty.
3861    fn rat_cert() -> (Vec<Vec<i64>>, Vec<LratStep>) {
3862        let cnf = vec![vec![1, 2], vec![-1, 3], vec![2], vec![-2]];
3863        let proof = vec![
3864            LratStep {
3865                id: 5,
3866                literals: vec![-1, -2],
3867                hints: vec![],
3868                rat_hints: vec![],
3869            },
3870            LratStep {
3871                id: 6,
3872                literals: vec![],
3873                hints: vec![3, 4],
3874                rat_hints: vec![],
3875            },
3876        ];
3877        (cnf, proof)
3878    }
3879
3880    #[test]
3881    fn blocked_clause_step_verifies_as_rat() {
3882        let (cnf, proof) = rat_cert();
3883        let r = verify_unsat_cert(&cnf, &proof);
3884        assert!(r.ok, "{}", r.message);
3885    }
3886
3887    #[test]
3888    fn rat_step_with_unhinted_resolvent_is_rejected() {
3889        // Add (1 -3) to the cnf: now clauses containing pivot-negation 1
3890        // are (1 2) [tautological resolvent, fine] AND (1 -3), whose
3891        // resolvent (-1 -2 -3) is NOT tautological and has no supplied
3892        // hints — the step must be refused, never guessed through.
3893        let (mut cnf, proof) = rat_cert();
3894        cnf.push(vec![1, -3]);
3895        let r = verify_unsat_cert(&cnf, &proof);
3896        assert!(!r.ok);
3897        assert!(
3898            r.message.contains("neither RUP-implied nor RAT"),
3899            "{}",
3900            r.message
3901        );
3902    }
3903
3904    #[test]
3905    fn rat_with_supplied_resolvent_hints_verifies() {
3906        // Same extended cnf, but the step now supplies hints proving the
3907        // (1 -3) resolvent (-1 -2 -3) is RUP: falsify 1=T,2=T,3=T; then
3908        // clause (-2) [id 4] conflicts immediately.
3909        let (mut cnf, mut proof) = rat_cert();
3910        cnf.push(vec![1, -3]); // becomes clause id 5
3911        proof[0].id = 6;
3912        proof[0].rat_hints = vec![(5, vec![4])];
3913        proof[1].id = 7;
3914        let r = verify_unsat_cert(&cnf, &proof);
3915        assert!(r.ok, "{}", r.message);
3916    }
3917
3918    #[test]
3919    fn unit_fraction_decomp_checks_exactness_coverage_and_ordering() {
3920        let c = |n, x, y, z| UnitFractionCase { n, x, y, z };
3921        // 4/3 = 1/1+1/4+1/12, 4/4 = 1/2+1/3+1/6, 4/5 = 1/2+1/4+1/20 (all exact, x<y<z).
3922        let good = vec![c(3, 1, 4, 12), c(4, 2, 3, 6), c(5, 2, 4, 20)];
3923        assert!(verify_unit_fraction_decomp(5, &good).ok);
3924        // A gap (missing n=4) fails coverage.
3925        assert!(!verify_unit_fraction_decomp(5, &[c(3, 1, 4, 12), c(5, 2, 4, 20)]).ok);
3926        // Inexact arithmetic fails (1/1+1/4+1/13 != 4/3).
3927        assert!(!verify_unit_fraction_decomp(3, &[c(3, 1, 4, 13)]).ok);
3928        // Non-distinct / non-ordered fails (y == z).
3929        assert!(!verify_unit_fraction_decomp(4, &[c(3, 1, 4, 12), c(4, 2, 6, 6)]).ok);
3930        // Out-of-range n fails.
3931        assert!(!verify_unit_fraction_decomp(3, &[c(3, 1, 4, 12), c(7, 2, 4, 28)]).ok);
3932    }
3933
3934    #[test]
3935    fn distinct_partial_sums_checks_validity_coverage_and_primality() {
3936        // p = 3, F_3\{0} = {1,2}. Subsets {1},{2},{1,2}; expected 2^2-1 = 3.
3937        // [1]->(1); [2]->(2); [1,2]->(1,0) all distinct mod 3.
3938        let full = vec![vec![1u64], vec![2], vec![1, 2]];
3939        assert!(verify_distinct_partial_sums(3, &full).ok);
3940        // Missing {2} -> incomplete coverage.
3941        assert!(!verify_distinct_partial_sums(3, &[vec![1u64], vec![1, 2]]).ok);
3942        // A repeated partial sum: [3,3] is moot; use p=5, ordering [1,4] -> (1,0) ok,
3943        // but [2,3] -> (2,0) ok; force a bad one: [1,2,2] invalid (repeat elt). Test a
3944        // genuine repeated-sum: in F_5, [4,1] -> (4,0); [1,4] -> (1,0); both fine.
3945        // Repeated partial sum example: subset {2,3} in F_5 ordered [2,3] -> (2,0); fine.
3946        // Construct an explicit repeat: ordering [1,4,5%? ] — instead test out-of-range.
3947        assert!(!verify_distinct_partial_sums(3, &[vec![1u64], vec![2], vec![1, 5]]).ok);
3948        // Non-prime p fails.
3949        assert!(!verify_distinct_partial_sums(4, &[vec![1u64]]).ok);
3950    }
3951
3952    #[test]
3953    fn powerful_triples_none_confirms_no_triple_and_counts_pairs() {
3954        // No three consecutive powerful integers up to 1000 (true).
3955        let r = verify_powerful_triples_none(1000, None);
3956        assert!(r.ok, "{}", r.message);
3957        // (8,9) is a consecutive powerful pair, so at least one exists.
3958        assert!(r.message.contains("pairs exist"));
3959        // A wrong pairs_claimed is rejected.
3960        assert!(!verify_powerful_triples_none(1000, Some(0)).ok);
3961        // 8 = 2^3 powerful, 9 = 3^2 powerful, 7 = prime not powerful: the pair
3962        // (8,9) is found but never a triple.
3963        assert!(verify_powerful_triples_none(10, None).ok);
3964    }
3965
3966    #[test]
3967    fn two_full_three_full_finds_the_complete_set() {
3968        // No 2-full n with n+1 3-full in [1,100] (3-full n+1 in {8,16,27,32,64,81}
3969        // give n in {7,15,26,31,63,80}, none powerful).
3970        assert!(verify_two_full_three_full(100, &[]).ok);
3971        // A spurious claim is rejected.
3972        assert!(!verify_two_full_three_full(100, &[8]).ok);
3973        // A missing example is rejected: if any exists in range, [] must fail.
3974        // (Construct via a tiny range where the set is known empty -> [] passes.)
3975        assert!(verify_two_full_three_full(10, &[]).ok);
3976    }
3977
3978    // Smallest prime p > n for which (n!+1) is a non-residue mod p (mirrors the
3979    // #398 generator); used to build a valid certificate inside the test.
3980    fn brocard_witness(n: u64) -> u64 {
3981        fn is_prime(n: u64) -> bool {
3982            if n < 2 {
3983                return false;
3984            }
3985            let mut d = 2;
3986            while d * d <= n {
3987                if n.is_multiple_of(d) {
3988                    return false;
3989                }
3990                d += 1;
3991            }
3992            true
3993        }
3994        fn modpow(mut b: u128, mut e: u128, m: u128) -> u128 {
3995            let mut r = 1u128;
3996            b %= m;
3997            while e > 0 {
3998                if e & 1 == 1 {
3999                    r = r * b % m;
4000                }
4001                e >>= 1;
4002                b = b * b % m;
4003            }
4004            r
4005        }
4006        let mut p = n + 1;
4007        loop {
4008            if is_prime(p) {
4009                let pm = p as u128;
4010                let mut f = 1u128;
4011                for k in 1..=n {
4012                    f = f * (k as u128) % pm;
4013                }
4014                let r = (f + 1) % pm;
4015                if r != 0 && modpow(r, (pm - 1) / 2, pm) == pm - 1 {
4016                    return p;
4017                }
4018            }
4019            p += 1;
4020        }
4021    }
4022
4023    #[test]
4024    fn brocard_no_square_certifies_a_range_and_rejects_tampering() {
4025        // [8,40]: all non-exceptions, each with a generated witnessing prime.
4026        let (n_min, n_max) = (8u64, 40u64);
4027        let cases: Vec<BrocardCase> = (n_min..=n_max)
4028            .map(|n| BrocardCase {
4029                n,
4030                p: brocard_witness(n),
4031            })
4032            .collect();
4033        let w = Witness::BrocardNoSquare {
4034            n_min,
4035            n_max,
4036            cases: cases.clone(),
4037        };
4038        let r = verify_witness(&w);
4039        assert!(r.ok, "should certify [{n_min},{n_max}]: {}", r.message);
4040
4041        // The known-solution branch: [4,7] has squares at 4,5,7 and a non-square at 6.
4042        let known = Witness::BrocardNoSquare {
4043            n_min: 4,
4044            n_max: 7,
4045            cases: vec![
4046                BrocardCase { n: 4, p: 0 },
4047                BrocardCase { n: 5, p: 0 },
4048                BrocardCase {
4049                    n: 6,
4050                    p: brocard_witness(6),
4051                },
4052                BrocardCase { n: 7, p: 0 },
4053            ],
4054        };
4055        assert!(
4056            verify_witness(&known).ok,
4057            "4,5,7 are the known squares; 6 is not"
4058        );
4059
4060        // Tamper 1: a composite "witnessing prime" must be rejected.
4061        let mut bad = cases.clone();
4062        bad[0].p = bad[0].n * (bad[0].n + 1); // composite, > n
4063        assert!(
4064            !verify_witness(&Witness::BrocardNoSquare {
4065                n_min,
4066                n_max,
4067                cases: bad,
4068            })
4069            .ok,
4070            "a non-prime witness must fail"
4071        );
4072        // Tamper 2: dropping a case breaks coverage.
4073        let short: Vec<BrocardCase> = cases[1..].to_vec();
4074        assert!(
4075            !verify_witness(&Witness::BrocardNoSquare {
4076                n_min,
4077                n_max,
4078                cases: short,
4079            })
4080            .ok,
4081            "incomplete coverage must fail"
4082        );
4083        // Tamper 3: claiming a non-exception n is a known square fails (n=8 not in {4,5,7}).
4084        assert!(
4085            !verify_witness(&Witness::BrocardNoSquare {
4086                n_min: 8,
4087                n_max: 8,
4088                cases: vec![BrocardCase { n: 8, p: 0 }],
4089            })
4090            .ok,
4091            "n=8 with no witnessing prime must fail (8 is not a known square and p=0 invalid)"
4092        );
4093    }
4094
4095    #[test]
4096    fn semiprime_egyptian_checks_decompositions_and_rejections() {
4097        // Hand-verified distinct-semiprime Egyptian expansions:
4098        //   1/6 = [6];  4/15 = 1/6+1/10;  7/30 = 1/6+1/15;  1/3 = 1/6+1/10+1/15.
4099        let good = Witness::SemiprimeEgyptian {
4100            cases: vec![
4101                SemiprimeEgyptianCase {
4102                    a: 1,
4103                    b: 6,
4104                    denominators: vec![6],
4105                },
4106                SemiprimeEgyptianCase {
4107                    a: 4,
4108                    b: 15,
4109                    denominators: vec![6, 10],
4110                },
4111                SemiprimeEgyptianCase {
4112                    a: 7,
4113                    b: 30,
4114                    denominators: vec![6, 15],
4115                },
4116                SemiprimeEgyptianCase {
4117                    a: 1,
4118                    b: 3,
4119                    denominators: vec![6, 10, 15],
4120                },
4121            ],
4122        };
4123        let r = verify_witness(&good);
4124        assert!(r.ok, "valid semiprime-Egyptian cases: {}", r.message);
4125
4126        // A non-semiprime denominator (12 = 2^2*3, not squarefree) is rejected.
4127        assert!(
4128            !verify_semiprime_egyptian(&[SemiprimeEgyptianCase {
4129                a: 1,
4130                b: 12,
4131                denominators: vec![12],
4132            }])
4133            .ok,
4134            "12 is not a squarefree semiprime"
4135        );
4136        // 30 = 2*3*5 has THREE prime factors -> rejected.
4137        assert!(
4138            !verify_semiprime_egyptian(&[SemiprimeEgyptianCase {
4139                a: 1,
4140                b: 30,
4141                denominators: vec![30],
4142            }])
4143            .ok,
4144            "30 has three prime factors"
4145        );
4146        // A sum that does not equal a/b is rejected (1/6 != 1/5).
4147        assert!(
4148            !verify_semiprime_egyptian(&[SemiprimeEgyptianCase {
4149                a: 1,
4150                b: 5,
4151                denominators: vec![6],
4152            }])
4153            .ok,
4154            "1/6 != 1/5"
4155        );
4156        // Non-increasing denominators are rejected.
4157        assert!(
4158            !verify_semiprime_egyptian(&[SemiprimeEgyptianCase {
4159                a: 4,
4160                b: 15,
4161                denominators: vec![10, 6],
4162            }])
4163            .ok,
4164            "denominators must be strictly increasing"
4165        );
4166        // A non-squarefree target denominator b is rejected (b=12).
4167        assert!(
4168            !verify_semiprime_egyptian(&[SemiprimeEgyptianCase {
4169                a: 1,
4170                b: 12,
4171                denominators: vec![14, 21],
4172            }])
4173            .ok,
4174            "b=12 is not squarefree"
4175        );
4176    }
4177}