Skip to main content

Crate vela_verify

Crate vela_verify 

Source
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§

BrocardCase
One (n, p) case of an Erdős #398 (Brocard) finite-confirmation certificate. For n ∉ {4,5,7}, p is a prime > n that WITNESSES that n! + 1 is not a perfect square: the verifier recomputes r = (n! + 1) mod p and confirms r is a quadratic NON-residue mod p (Euler’s criterion), which forces n! + 1 to be a non-square (a perfect square is a residue, or 0, mod every prime). For the three known solutions n ∈ {4,5,7}, p is ignored and the verifier confirms n! + 1 IS the recorded perfect square (25, 121, 5041).
CrtCoverRow
One prime row of an Erdős #203 partial-cover certificate.
DeficiencyEntry
One (k, N, delta, slots) entry of an Erdős #1093 deficiency certificate. n is a decimal string (up to 38 digits / u128); slots is optional — when absent only the count is checked.
Faithfulness
The frozen faithfulness verdict: does witness ESTABLISH the claim in assertion_text? This is the load-bearing, un-forgeable check the exact-lane auto-admission rests on. verify_witness only confirms a witness is INTERNALLY valid (a genuine Sidon set of size points.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 pass verify_witness. claim_witness_faithful closes that: it re-derives faithfulness from frozen inputs (the parsed assertion + the witness structure), never from the drafter-set match_to_claim.matches flag an agent can author. faithful is true only when the witness both verifies AND its parameters meet/exceed the parsed claim.
KummerEntry
One (k, m) entry of an Erdős #684 certificate.
LratStep
One addition step of an LRAT proof: clause id is the listed literals (empty = the empty clause = the proof goal), justified by reverse unit propagation over the antecedent clause hints in order.
MinGcdCase
One (n, f) case of an Erdős #700 certificate.
ParsedClaim
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_claim returns None for anything it cannot read unambiguously, so an unrecognized assertion is never faithful (fail-closed).
SemiprimeEgyptianCase
One (a, b, denominators) case of an Erdős #306 certificate: an Egyptian expansion a/b = 1/n_1 + ... + 1/n_k in which every n_i is a product of two DISTINCT primes (a squarefree semiprime), with b squarefree and the n_i strictly increasing. Verified with exact integer arithmetic.
UnitFractionCase
One (n, x, y, z) case of an Erdős #242 (Erdős–Straus) certificate: 4/n = 1/x + 1/y + 1/z with 1 <= x < y < z.
VerifyResult
The outcome of verifying one witness.

Enums§

Witness
A witness to verify. Tagged by kind on 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_admitted audit record (verifier_env_hash) so an auditor can pin which frozen vela-verify produced 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_verified claim (with the prose shown only as an unverified description), so author prose cannot puff a true bound into a false headline. None for kinds that are not floor-admissible. Mirrors the binding in claim_witness_faithful (kind, n, the bound-defining parameters, size).
claim_witness_faithful
Frozen check that witness establishes the claim in assertion_text. See Faithfulness for 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 yields faithful: false.
dominates
Verify a witness against its exact verifier, plus the optional claimed_size cross-check. Machine-checked novelty: does new strictly dominate prior for 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 returns None on 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 prime p and strictly increasing cuts c_0 < ... < c_k such 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_h set in {0,1}^n: all sums of h elements (with repetition, non-decreasing index order) distinct. h = 2 is Sidon.
verify_binom_deficiency
Verify an Erdős #1093 (ELS93) deficiency certificate: each entry’s C(N,k) is Kummer-defined and delta(N,k) (and slot positions, when given) recompute exactly. N may 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) for k <= k_max and 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], confirm n! + 1 is a perfect square for exactly the known n ∈ {4,5,7} and for no other n. Each non-exception n carries a witnessing prime p > n and the verifier recomputes r = (n! + 1) mod p (iterated modular product — n! is never materialised, so no bignum) and confirms via Euler’s criterion that r is a quadratic NON-residue mod p, which forces n! + 1 to be a non-square. Fail-closed: a non-prime / too-small p, a residue r, r = 0, a wrong known-solution, or incomplete coverage of [n_min, n_max] aborts. A finite confirmation (the conjecture over all n is 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 exactly w, pairwise Hamming distance >= d.
verify_costas
A Costas array: a permutation p of consecutive integers such that the displacement vectors (j-i, p[j]-p[i]) for i < j are distinct.
verify_covering
A covering design C(v, k, t): blocks are k-subsets of [0, v) such that every t-subset of [0, v) is contained in at least one.
verify_crt_partial_cover
Verify an Erdős #203 partial CRT covering certificate. m is a decimal string coprime to 6; each row pins a prime p, the orders of 2 and 3 mod p, h = lcm(ord2, ord3), t_p = (-m^-1) mod p, m mod p, and an affine line such that p | 2^k 3^l m + 1 iff alpha*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: rows of 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 that orderings give, for EVERY nonempty A ⊆ F_p\{0}, a rearrangement of A whose partial sums are all distinct mod p. Fail-closed: a non-prime p, an out-of-range element, a non-distinct partial-sum sequence, or incomplete coverage of the 2^(p-1) - 1 nonempty subsets aborts. Certifies #475 for this p (a finite confirmation; the question over all primes is open).
verify_gf2_sidon
Verify a Sidon set in GF(2)^n (OEIS A394031): elements are 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 reference is_gf2_sidon; pure integer arithmetic.
verify_golomb
verify_interval_product
verify_kummer_no_carry
Verify an Erdős #684 certificate: for each (k, m), recompute m = prod_{p<=k} p^(floor(log_p k)+1) and confirm zero Kummer carries adding j + (m-1-j) in base p for all 2 <= j <= k, p <= j — hence no prime p <= j divides C(m-1, j) and f(m-1) > k.
verify_linear_code
A linear [n, k, d]_q code given by a k x n generator matrix over a prime field GF(q). Verifies rank(G) = k and that the true minimum distance (min nonzero codeword weight, by exhaustive enumeration of the q^k codewords, guarded) is >= claimed_d. Prime-power GF(q) is refused rather than mis-verified.
verify_min_binom_gcd
Verify an Erdős #700 value certificate: for each (n, f), recompute f(n) = min_{1<k<=n/2} gcd(n, C(n,k)) via the Kummer identity gcd(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): perm is a permutation of 1..=n (one rook per row, distinct columns), and the count of distinct direction classes sorted(|Δcol|,|Δrow|)/gcd over all rook pairs equals claimed (when given). Certifies the lower bound a(n) >= count only.
verify_semiprime_egyptian
Erdős #306: verify each listed reduced a/b (with b squarefree) is exhibited as an Egyptian expansion a/b = sum 1/n_i whose denominators n_i are all products of two DISTINCT primes (squarefree semiprimes), strictly increasing. Exact integer arithmetic (reduced-fraction accumulation, no floats). Fail-closed: a non-squarefree b, 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}^n under componentwise integer addition: all pairwise sums a+b (a <= b) distinct.
verify_two_full_three_full
Erdős #366: verify examples is EXACTLY the set of n in [1, n_max] that are 2-full (powerful: every prime exponent >= 2) with n+1 3-full (every prime exponent >= 3). Re-scans [1, n_max] via an SPF sieve (the minimum prime exponent is computed exactly). An empty examples is a finite confirmation that no such n exists up to n_max; a nonempty examples exhibits genuine witnesses. Fail-closed: a claimed example that is not such an n, or a missing one, aborts.
verify_union_free
Verify a union-free family (OEIS A347025): sets are 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 cases give, for EVERY n in [3, n_max], distinct 1 <= x < y < z with 4/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 all 3 <= n <= n_max (a FINITE confirmation; the uniform proof over all n is the open problem). Exact u128 integer 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.