Expand description
Frozen, independent exact verifiers for combinatorial and coding-theory witnesses.
The discovery loop’s proposers are untrusted: an agent returns an explicit construction (a set of points, a ruler, a generator matrix), and this crate re-checks it deterministically before any claim is recorded. A witness that does not pass here is discarded no matter what the proposer reported. Corrupting a witness must fail the verifier — that is the property the self-tests pin.
This is the reference verifier registry the trust gate
([vela_protocol::verifier_attachment]) and vela reproduce build
on: a passing verify here is the evidence an exact_construction
verifier attachment attests to. The verifiers are intentionally
dependency-light (serde only) and pure — no I/O, no randomness — so a
third party can re-run them and get byte-identical verdicts.
Ported from the campaign’s scripts/verify_construction.py; the
Python reference and this Rust port must agree on every witness.
Structs§
- Brocard
Case - One
(n, p)case of an Erdős #398 (Brocard) finite-confirmation certificate. Forn ∉ {4,5,7},pis a prime> nthat WITNESSES thatn! + 1is not a perfect square: the verifier recomputesr = (n! + 1) mod pand confirmsris a quadratic NON-residue modp(Euler’s criterion), which forcesn! + 1to be a non-square (a perfect square is a residue, or0, mod every prime). For the three known solutionsn ∈ {4,5,7},pis ignored and the verifier confirmsn! + 1IS the recorded perfect square (25, 121, 5041). - CrtCover
Row - One prime row of an Erdős #203 partial-cover certificate.
- Deficiency
Entry - One
(k, N, delta, slots)entry of an Erdős #1093 deficiency certificate.nis a decimal string (up to 38 digits / u128);slotsis optional — when absent only the count is checked. - Faithfulness
- The frozen faithfulness verdict: does
witnessESTABLISH the claim inassertion_text? This is the load-bearing, un-forgeable check the exact-lane auto-admission rests on.verify_witnessonly confirms a witness is INTERNALLY valid (a genuine Sidon set of sizepoints.len()); it never reads the assertion, so an INFLATED assertion (“a(20) >= 2500”) over a valid-but-weaker witness (a real Sidon set of 1989 points) would passverify_witness.claim_witness_faithfulcloses that: it re-derives faithfulness from frozen inputs (the parsed assertion + the witness structure), never from the drafter-setmatch_to_claim.matchesflag an agent can author.faithfulis true only when the witness both verifies AND its parameters meet/exceed the parsed claim. - Kummer
Entry - One
(k, m)entry of an Erdős #684 certificate. - Lrat
Step - One addition step of an LRAT proof: clause
idis the listedliterals(empty = the empty clause = the proof goal), justified by reverse unit propagation over the antecedent clausehintsin order. - MinGcd
Case - One
(n, f)case of an Erdős #700 certificate. - Parsed
Claim - A claim parsed from a finding’s free-text assertion into the structured,
frozen-verifiable shape needed to BIND it to a witness. Deliberately
conservative:
parse_claimreturnsNonefor anything it cannot read unambiguously, so an unrecognized assertion is never faithful (fail-closed). - Semiprime
Egyptian Case - One
(a, b, denominators)case of an Erdős #306 certificate: an Egyptian expansiona/b = 1/n_1 + ... + 1/n_kin which everyn_iis a product of two DISTINCT primes (a squarefree semiprime), withbsquarefree and then_istrictly increasing. Verified with exact integer arithmetic. - Unit
Fraction Case - One
(n, x, y, z)case of an Erdős #242 (Erdős–Straus) certificate:4/n = 1/x + 1/y + 1/zwith1 <= x < y < z. - Verify
Result - The outcome of verifying one witness.
Enums§
- Witness
- A witness to verify. Tagged by
kindon the wire, so a witness file is{"kind": "sidon", "n": 8, "points": [[...], ...], ...}.
Constants§
- ENV_ID
- A stable, reproducible identity for the frozen verifier build, recorded in
the
policy.auto_admittedaudit record (verifier_env_hash) so an auditor can pin which frozenvela-verifyproduced a machine admission. Same source
Functions§
- canonical_
claim - The canonical, WITNESS-DERIVED verified claim for a floor-admissible witness:
exactly the lower bound the witness structurally establishes, independent of
the author’s assertion prose. Surfaces should DISPLAY this as the verified
machine_verifiedclaim (with the prose shown only as an unverified description), so author prose cannot puff a true bound into a false headline.Nonefor kinds that are not floor-admissible. Mirrors the binding inclaim_witness_faithful(kind, n, the bound-defining parameters, size). - claim_
witness_ faithful - Frozen check that
witnessestablishes the claim inassertion_text. SeeFaithfulnessfor why this is the un-forgeable core of the exact lane. Fail-closed throughout: any parse miss, kind/dimension mismatch, size shortfall, or internal-validity failure yieldsfaithful: false. - dominates
- Verify a witness against its exact verifier, plus the optional
claimed_sizecross-check. Machine-checked novelty: doesnewstrictly dominatepriorfor kinds with a natural order? Conservative: kinds without an obvious dominance order return Err (the caller reports “not comparable”) — never a silent pass. This is the anti-AI-novelty-judge: dominance is arithmetic, not opinion. - parse_
claim - Parse a finding assertion into a
ParsedClaim. Conservative and fail-closed: recognizes only the lower-bound forms the exact lane admits, and returnsNoneon any ambiguity (no kind keyword, no parseable bound, an equality/optimality marker, two disagreeing dimension signals, or a lower bound co-occurring with an equality marker). - verify_
balanced_ coloring - A Golomb ruler: integer marks with all
C(m,2)pairwise differences distinct. Verify an Erdős #1056 cut-equality certificate: a primepand strictly increasing cutsc_0 < ... < c_ksuch that every consecutive interval(c_{i-1}, c_i]has integer product== 1 (mod p). Pure modular arithmetic — deterministic and total, no search. Erdős #617 witness shape: a balanced r-coloring of K_n. Checks that every edge {i,j} (i<j, 0-indexed) is colored in 1..=r and that every (r+1)-subset of vertices sees ALL r colors among its internal edges. - verify_
bh - A
B_hset in{0,1}^n: all sums ofhelements (with repetition, non-decreasing index order) distinct.h = 2is Sidon. - verify_
binom_ deficiency - Verify an Erdős #1093 (ELS93) deficiency certificate: each entry’s
C(N,k)is Kummer-defined anddelta(N,k)(and slot positions, when given) recompute exactly.Nmay be up to 38 decimal digits. - verify_
binom_ exception_ enum - Verify an Erdős #1094 exception-enumeration certificate: re-enumerate
every candidate
N = x + k - r(x | gcd(lcm(1..k), r*C(k,r)),k | x,N >= 2k) fork <= k_maxand confirm the exception set equals the claimed(N, k)list exactly. - verify_
brocard_ no_ square - Erdős #398 (Brocard’s problem,
n! + 1 = m^2): over[n_min, n_max], confirmn! + 1is a perfect square for exactly the knownn ∈ {4,5,7}and for no othern. Each non-exceptionncarries a witnessing primep > nand the verifier recomputesr = (n! + 1) mod p(iterated modular product —n!is never materialised, so no bignum) and confirms via Euler’s criterion thatris a quadratic NON-residue modp, which forcesn! + 1to be a non-square. Fail-closed: a non-prime / too-smallp, a residuer,r = 0, a wrong known-solution, or incomplete coverage of[n_min, n_max]aborts. A finite confirmation (the conjecture over allnis the open problem). - verify_
cap - A cap in
F_3^n: no three distinct points sum to 0 mod 3 (no three collinear). For each pair, the unique line-completion must be absent. - verify_
constant_ weight - A constant-weight binary code
A(n, d, w): codewords of weight exactlyw, pairwise Hamming distance>= d. - verify_
costas - A Costas array: a permutation
pof consecutive integers such that the displacement vectors(j-i, p[j]-p[i])fori < jare distinct. - verify_
covering - A covering design
C(v, k, t): blocks arek-subsets of[0, v)such that everyt-subset of[0, v)is contained in at least one. - verify_
crt_ partial_ cover - Verify an Erdős #203 partial CRT covering certificate.
mis a decimal string coprime to 6; each row pins a primep, the orders of 2 and 3 modp,h = lcm(ord2, ord3),t_p = (-m^-1) mod p,m mod p, and an affine line such thatp | 2^k 3^l m + 1iffalpha*k + beta*l == gamma (mod h)— checked exhaustively over(k, l) in [0, h)^2. Deterministic and total. - verify_
diff_ triangle - Verify a difference triangle set:
rowsof strictly increasing non-negative integers, each starting at 0, with every positive within-row pairwise difference GLOBALLY distinct (no difference repeats across the whole set). Reports the scope (the largest mark).claimed_scope, when present, must equal the recomputed scope. - verify_
distinct_ partial_ sums - Erdős #475 (Graham distinct-partial-sums): for a fixed prime
p, verify thatorderingsgive, for EVERY nonemptyA ⊆ F_p\{0}, a rearrangement ofAwhose partial sums are all distinct modp. Fail-closed: a non-primep, an out-of-range element, a non-distinct partial-sum sequence, or incomplete coverage of the2^(p-1) - 1nonempty subsets aborts. Certifies #475 for thisp(a finite confirmation; the question over all primes is open). - verify_
gf2_ sidon - Verify a Sidon set in
GF(2)^n(OEIS A394031):elementsare integer bitmasks; the set is Sidon iff the elements are distinct and all pairwise XORs are distinct and nonzero (equivalently, no four distinct elements XOR to zero). Mirrors the referenceis_gf2_sidon; pure integer arithmetic. - verify_
golomb - verify_
interval_ product - verify_
kummer_ no_ carry - Verify an Erdős #684 certificate: for each
(k, m), recomputem = prod_{p<=k} p^(floor(log_p k)+1)and confirm zero Kummer carries addingj + (m-1-j)in basepfor all2 <= j <= k,p <= j— hence no primep <= jdividesC(m-1, j)andf(m-1) > k. - verify_
linear_ code - A linear
[n, k, d]_qcode given by ak x ngenerator matrix over a prime fieldGF(q). Verifiesrank(G) = kand that the true minimum distance (min nonzero codeword weight, by exhaustive enumeration of theq^kcodewords, guarded) is>= claimed_d. Prime-powerGF(q)is refused rather than mis-verified. - verify_
min_ binom_ gcd - Verify an Erdős #700 value certificate: for each
(n, f), recomputef(n) = min_{1<k<=n/2} gcd(n, C(n,k))via the Kummer identitygcd(n, C(n,k)) = prod_{p|n} p^min(v_p(n), carries_p(k, n-k)). - verify_
powerful_ triples_ none - Erdős #364: verify there are NO three consecutive powerful integers in
[1, n_max]. A smallest-prime-factor sieve over[2, n_max]makes the powerful test O(log n); the scan is fail-closed (any triple aborts). Finite confirmation (the question over all integers is open).pairs_claimed, if present, must equal the count of consecutive powerful pairs found. - verify_
rook_ directions - Verify a non-attacking rook placement (OEIS A321531):
permis a permutation of1..=n(one rook per row, distinct columns), and the count of distinct direction classessorted(|Δcol|,|Δrow|)/gcdover all rook pairs equalsclaimed(when given). Certifies the lower bound a(n) >= count only. - verify_
semiprime_ egyptian - Erdős #306: verify each listed reduced
a/b(withbsquarefree) is exhibited as an Egyptian expansiona/b = sum 1/n_iwhose denominatorsn_iare all products of two DISTINCT primes (squarefree semiprimes), strictly increasing. Exact integer arithmetic (reduced-fraction accumulation, no floats). Fail-closed: a non-squarefreeb, a denominator that is not a distinct-prime product, a non-increasing list, a mismatched sum, or a duplicated rational aborts. A per-instance finite confirmation (the question over all positive rationals is open). - verify_
sidon - A Sidon subset of
{0,1}^nunder componentwise integer addition: all pairwise sumsa+b(a <= b) distinct. - verify_
two_ full_ three_ full - Erdős #366: verify
examplesis EXACTLY the set ofnin[1, n_max]that are 2-full (powerful: every prime exponent>= 2) withn+13-full (every prime exponent>= 3). Re-scans[1, n_max]via an SPF sieve (the minimum prime exponent is computed exactly). An emptyexamplesis a finite confirmation that no suchnexists up ton_max; a nonemptyexamplesexhibits genuine witnesses. Fail-closed: a claimed example that is not such ann, or a missing one, aborts. - verify_
union_ free - Verify a union-free family (OEIS A347025):
setsare nonempty subsets of{1..n}and no member is the union of a sub-collection of the others. Polynomial check: a member C is expressible iff the union of every OTHER member that is a subset of C equals C (any super-C member would overshoot). Certifies the lower bound a(n) >= |sets| only. - verify_
unit_ fraction_ decomp - Erdős #242 (Erdős–Straus, distinct variant): verify that
casesgive, for EVERYnin[3, n_max], distinct1 <= x < y < zwith4/n = 1/x + 1/y + 1/z. Fail-closed: a gap in[3, n_max], a non-ordered triple, or an inexact equation aborts. Certifies the conjecture for all3 <= n <= n_max(a FINITE confirmation; the uniform proof over allnis the open problem). Exactu128integer arithmetic, no floating point. - verify_
unsat_ cert - Verify an UNSAT certificate: replay the LRAT proof over the CNF and confirm it derives the empty clause. Each step’s added clause must be RUP-implied by the clauses available so far (original + previously added). Deterministic and total; bounded by explicit guards.
- verify_
witness - verify_
witness_ with_ claim - Verify the witness and bind an exact claim with one mechanical pass.