use std::collections::HashSet;
use serde::{Deserialize, Serialize};
pub const ENV_ID: &str = concat!("vela-verify@", env!("CARGO_PKG_VERSION"));
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct VerifyResult {
pub ok: bool,
pub message: String,
#[serde(default, skip_serializing_if = "Option::is_none")]
pub value: Option<f64>,
}
impl VerifyResult {
pub fn ok(message: impl Into<String>) -> Self {
Self {
ok: true,
message: message.into(),
value: None,
}
}
pub fn fail(message: impl Into<String>) -> Self {
Self {
ok: false,
message: message.into(),
value: None,
}
}
}
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
#[serde(tag = "kind", rename_all = "snake_case")]
pub enum Witness {
Sidon {
n: usize,
points: Vec<Vec<i64>>,
#[serde(default, skip_serializing_if = "Option::is_none")]
claimed_size: Option<usize>,
},
Golomb { marks: Vec<i64> },
Cap {
n: usize,
points: Vec<Vec<i64>>,
#[serde(default, skip_serializing_if = "Option::is_none")]
claimed_size: Option<usize>,
},
Bh {
n: usize,
h: usize,
points: Vec<Vec<i64>>,
#[serde(default, skip_serializing_if = "Option::is_none")]
claimed_size: Option<usize>,
},
Covering {
v: usize,
k: usize,
t: usize,
blocks: Vec<Vec<usize>>,
},
ConstantWeight {
n: usize,
d: usize,
w: usize,
words: Vec<Vec<i64>>,
#[serde(default, skip_serializing_if = "Option::is_none")]
claimed_size: Option<usize>,
},
Costas { perm: Vec<i64> },
Gf2Sidon {
elements: Vec<u64>,
#[serde(default, skip_serializing_if = "Option::is_none")]
claimed_size: Option<usize>,
},
UnionFree {
n: usize,
sets: Vec<Vec<u32>>,
#[serde(default, skip_serializing_if = "Option::is_none")]
claimed_size: Option<usize>,
},
RookDirections {
n: usize,
perm: Vec<i64>,
#[serde(default, skip_serializing_if = "Option::is_none")]
claimed_directions: Option<usize>,
},
LinearCode {
q: u64,
claimed_d: usize,
generator: Vec<Vec<i64>>,
},
IntervalProduct { p: u64, cuts: Vec<u64> },
BalancedColoring {
n: usize,
r: usize,
edge_colors: std::collections::BTreeMap<String, u32>,
},
CrtPartialCover { m: String, rows: Vec<CrtCoverRow> },
KummerNoCarry { entries: Vec<KummerEntry> },
MinBinomGcd { cases: Vec<MinGcdCase> },
BinomDeficiency { entries: Vec<DeficiencyEntry> },
BinomExceptionEnum {
k_max: u64,
exceptions: Vec<(u64, u64)>,
},
UnsatCert {
cnf: Vec<Vec<i64>>,
proof: Vec<LratStep>,
},
DiffTriangle {
rows: Vec<Vec<i64>>,
#[serde(default, skip_serializing_if = "Option::is_none")]
claimed_scope: Option<usize>,
},
UnitFractionDecomp {
n_max: u64,
cases: Vec<UnitFractionCase>,
},
DistinctPartialSums { p: u64, orderings: Vec<Vec<u64>> },
PowerfulTriplesNone {
n_max: u64,
#[serde(default, skip_serializing_if = "Option::is_none")]
pairs_claimed: Option<u64>,
},
TwoFullThreeFull { n_max: u64, examples: Vec<u64> },
BrocardNoSquare {
n_min: u64,
n_max: u64,
cases: Vec<BrocardCase>,
},
SemiprimeEgyptian { cases: Vec<SemiprimeEgyptianCase> },
}
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct LratStep {
pub id: u64,
pub literals: Vec<i64>,
pub hints: Vec<u64>,
#[serde(default, skip_serializing_if = "Vec::is_empty")]
pub rat_hints: Vec<(u64, Vec<u64>)>,
}
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct CrtCoverRow {
pub p: u64,
pub ord2: u64,
pub ord3: u64,
pub h: u64,
pub t_p: u64,
pub m_mod_p: u64,
pub line: [u64; 4],
}
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct KummerEntry {
pub k: u64,
pub m: u64,
}
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct MinGcdCase {
pub n: u64,
pub f: u64,
}
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct UnitFractionCase {
pub n: u64,
pub x: u64,
pub y: u64,
pub z: u64,
}
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct BrocardCase {
pub n: u64,
#[serde(default)]
pub p: u64,
}
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct SemiprimeEgyptianCase {
pub a: u64,
pub b: u64,
pub denominators: Vec<u64>,
}
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct DeficiencyEntry {
pub k: u64,
pub n: String,
pub delta: u64,
#[serde(default, skip_serializing_if = "Option::is_none")]
pub slots: Option<Vec<u64>>,
}
impl Witness {
pub fn kind(&self) -> &'static str {
match self {
Witness::Sidon { .. } => "sidon",
Witness::Golomb { .. } => "golomb",
Witness::Cap { .. } => "cap",
Witness::Bh { .. } => "bh",
Witness::Covering { .. } => "covering",
Witness::ConstantWeight { .. } => "constant_weight",
Witness::Costas { .. } => "costas",
Witness::Gf2Sidon { .. } => "gf2_sidon",
Witness::UnionFree { .. } => "union_free",
Witness::RookDirections { .. } => "rook_directions",
Witness::LinearCode { .. } => "linear_code",
Witness::IntervalProduct { .. } => "interval_product",
Witness::BalancedColoring { .. } => "balanced_coloring",
Witness::CrtPartialCover { .. } => "crt_partial_cover",
Witness::KummerNoCarry { .. } => "kummer_no_carry",
Witness::MinBinomGcd { .. } => "min_binom_gcd",
Witness::BinomDeficiency { .. } => "binom_deficiency",
Witness::BinomExceptionEnum { .. } => "binom_exception_enum",
Witness::UnsatCert { .. } => "unsat_cert",
Witness::DiffTriangle { .. } => "diff_triangle",
Witness::UnitFractionDecomp { .. } => "unit_fraction_decomp",
Witness::DistinctPartialSums { .. } => "distinct_partial_sums",
Witness::PowerfulTriplesNone { .. } => "powerful_triples_none",
Witness::TwoFullThreeFull { .. } => "two_full_three_full",
Witness::BrocardNoSquare { .. } => "brocard_no_square",
Witness::SemiprimeEgyptian { .. } => "semiprime_egyptian",
}
}
}
pub fn verify_diff_triangle(rows: &[Vec<i64>], claimed_scope: Option<usize>) -> VerifyResult {
if rows.is_empty() {
return VerifyResult::fail("empty difference triangle set");
}
let mut diffs: HashSet<i64> = HashSet::new();
let mut diff_count = 0usize;
let mut scope: i64 = 0;
for (r, row) in rows.iter().enumerate() {
if row.len() < 2 {
return VerifyResult::fail(format!("row {r} has fewer than 2 marks"));
}
if row[0] != 0 {
return VerifyResult::fail(format!("row {r} does not start at 0"));
}
for w in row.windows(2) {
if w[1] <= w[0] {
return VerifyResult::fail(format!("row {r} is not strictly increasing"));
}
}
scope = scope.max(*row.last().unwrap());
for i in 0..row.len() {
for j in (i + 1)..row.len() {
let d = row[j] - row[i];
if !diffs.insert(d) {
return VerifyResult::fail(format!(
"difference {d} repeats (row {r}) — not a difference triangle set"
));
}
diff_count += 1;
}
}
}
let scope_usize = scope as usize;
if let Some(c) = claimed_scope
&& c != scope_usize
{
return VerifyResult::fail(format!(
"verifier passed but scope {scope_usize} != claimed_scope {c}"
));
}
VerifyResult::ok(format!(
"difference triangle set: {} rows, scope {scope_usize}, all {diff_count} within-row differences globally distinct",
rows.len()
))
}
pub fn dominates(new: &Witness, prior: &Witness) -> Result<bool, String> {
use Witness::*;
match (new, prior) {
(
Sidon {
n: n1, points: p1, ..
},
Sidon {
n: n2, points: p2, ..
},
) => {
if n1 != n2 {
return Err(format!("different n ({n1} vs {n2}); not comparable"));
}
Ok(p1.len() > p2.len())
}
(Golomb { marks: m1, .. }, Golomb { marks: m2, .. }) => Ok(m1.len() > m2.len()),
(BalancedColoring { n: n1, r: r1, .. }, BalancedColoring { n: n2, r: r2, .. }) => {
if r1 != r2 {
return Err(format!("different r ({r1} vs {r2}); not comparable"));
}
Ok(n1 > n2)
}
(IntervalProduct { p: p1, cuts: c1 }, IntervalProduct { p: p2, cuts: c2 }) => {
if p1 == p2 {
Ok(c1.len() > c2.len())
} else {
Ok(c1.len() > c2.len())
}
}
_ => Err(format!(
"no dominance order defined between {} and {}",
new.kind(),
prior.kind()
)),
}
}
pub fn verify_witness(witness: &Witness) -> VerifyResult {
match witness {
Witness::Sidon {
n,
points,
claimed_size,
} => with_size(verify_sidon(points, *n), points.len(), *claimed_size),
Witness::Golomb { marks } => verify_golomb(marks),
Witness::Cap {
n,
points,
claimed_size,
} => with_size(verify_cap(points, *n), points.len(), *claimed_size),
Witness::Bh {
n,
h,
points,
claimed_size,
} => with_size(verify_bh(points, *n, *h), points.len(), *claimed_size),
Witness::Covering { v, k, t, blocks } => verify_covering(blocks, *v, *k, *t),
Witness::IntervalProduct { p, cuts } => verify_interval_product(*p, cuts),
Witness::BalancedColoring { n, r, edge_colors } => {
verify_balanced_coloring(*n, *r, edge_colors)
}
Witness::CrtPartialCover { m, rows } => verify_crt_partial_cover(m, rows),
Witness::KummerNoCarry { entries } => verify_kummer_no_carry(entries),
Witness::MinBinomGcd { cases } => verify_min_binom_gcd(cases),
Witness::BinomDeficiency { entries } => verify_binom_deficiency(entries),
Witness::BinomExceptionEnum { k_max, exceptions } => {
verify_binom_exception_enum(*k_max, exceptions)
}
Witness::UnsatCert { cnf, proof } => verify_unsat_cert(cnf, proof),
Witness::ConstantWeight {
n,
d,
w,
words,
claimed_size,
} => with_size(
verify_constant_weight(words, *n, *d, *w),
words.len(),
*claimed_size,
),
Witness::Costas { perm } => verify_costas(perm),
Witness::Gf2Sidon {
elements,
claimed_size,
} => with_size(verify_gf2_sidon(elements), elements.len(), *claimed_size),
Witness::UnionFree {
n,
sets,
claimed_size,
} => with_size(verify_union_free(*n, sets), sets.len(), *claimed_size),
Witness::RookDirections {
n,
perm,
claimed_directions,
} => verify_rook_directions(*n, perm, *claimed_directions),
Witness::LinearCode {
q,
claimed_d,
generator,
} => verify_linear_code(generator, *q, *claimed_d),
Witness::DiffTriangle {
rows,
claimed_scope,
} => verify_diff_triangle(rows, *claimed_scope),
Witness::UnitFractionDecomp { n_max, cases } => verify_unit_fraction_decomp(*n_max, cases),
Witness::DistinctPartialSums { p, orderings } => {
verify_distinct_partial_sums(*p, orderings)
}
Witness::PowerfulTriplesNone {
n_max,
pairs_claimed,
} => verify_powerful_triples_none(*n_max, *pairs_claimed),
Witness::TwoFullThreeFull { n_max, examples } => {
verify_two_full_three_full(*n_max, examples)
}
Witness::BrocardNoSquare {
n_min,
n_max,
cases,
} => verify_brocard_no_square(*n_min, *n_max, cases),
Witness::SemiprimeEgyptian { cases } => verify_semiprime_egyptian(cases),
}
}
pub fn verify_two_full_three_full(n_max: u64, examples: &[u64]) -> VerifyResult {
if n_max < 1 {
return VerifyResult::fail("n_max must be >= 1");
}
if n_max > 200_000_000 {
return VerifyResult::fail("n_max too large for the in-gate sieve (cap 2e8)");
}
let n = (n_max + 1) as usize; let mut spf = vec![0u32; n + 1];
for i in 2..=n {
if spf[i] == 0 {
let mut j = i;
while j <= n {
if spf[j] == 0 {
spf[j] = i as u32;
}
j += i;
}
}
}
let min_exp = |mut m: usize| -> u64 {
if m <= 1 {
return u64::MAX;
}
let mut lo = u64::MAX;
while m > 1 {
let p = spf[m] as usize;
let mut e = 0;
while m.is_multiple_of(p) {
m /= p;
e += 1;
}
lo = lo.min(e);
}
lo
};
let mut found: Vec<u64> = Vec::new();
for m in 1..=(n_max as usize) {
if min_exp(m) >= 2 && min_exp(m + 1) >= 3 {
found.push(m as u64);
}
}
let mut claimed = examples.to_vec();
claimed.sort_unstable();
if claimed != found {
return VerifyResult::fail(format!(
"claimed examples {claimed:?} != the {} actually found in [1, {n_max}]: {found:?}",
found.len()
));
}
if found.is_empty() {
VerifyResult::ok(format!(
"Erdős #366 finite confirmation: NO 2-full n with n+1 3-full in [1, {n_max}]. \
The question over all integers is the open problem."
))
} else {
VerifyResult::ok(format!(
"Erdős #366: {} genuine witness(es) in [1, {n_max}] — 2-full n with n+1 3-full: {found:?}. \
Exhibits existence (the set is complete over the range).",
found.len()
))
}
}
pub fn verify_powerful_triples_none(n_max: u64, pairs_claimed: Option<u64>) -> VerifyResult {
if n_max < 3 {
return VerifyResult::fail("n_max must be >= 3");
}
if n_max > 200_000_000 {
return VerifyResult::fail("n_max too large for the in-gate sieve (cap 2e8)");
}
let n = n_max as usize;
let mut spf = vec![0u32; n + 1];
for i in 2..=n {
if spf[i] == 0 {
let mut j = i;
while j <= n {
if spf[j] == 0 {
spf[j] = i as u32;
}
j += i;
}
}
}
let is_powerful = |mut m: usize| -> bool {
if m == 1 {
return true;
}
while m > 1 {
let p = spf[m] as usize;
let mut e = 0;
while m.is_multiple_of(p) {
m /= p;
e += 1;
}
if e < 2 {
return false;
}
}
true
};
let mut pairs = 0u64;
let mut prev = is_powerful(1);
let mut prev2 = false;
for m in 2..=n {
let cur = is_powerful(m);
if cur && prev {
pairs += 1;
}
if cur && prev && prev2 {
return VerifyResult::fail(format!(
"found three consecutive powerful integers ending at {m} (#364 would be FALSIFIED)"
));
}
prev2 = prev;
prev = cur;
}
if let Some(claimed) = pairs_claimed
&& claimed != pairs
{
return VerifyResult::fail(format!(
"pairs_claimed {claimed} != {pairs} consecutive powerful pairs actually found"
));
}
VerifyResult::ok(format!(
"Erdős #364 verified for [1, {n_max}]: no three consecutive powerful integers \
({pairs} consecutive powerful pairs exist, e.g. 8,9). Finite confirmation; the \
question over all integers is the open problem."
))
}
pub fn verify_distinct_partial_sums(p: u64, orderings: &[Vec<u64>]) -> VerifyResult {
let is_prime = |n: u64| -> bool {
if n < 2 {
return false;
}
let mut d = 2;
while d * d <= n {
if n.is_multiple_of(d) {
return false;
}
d += 1;
}
true
};
if !is_prime(p) {
return VerifyResult::fail(format!("p = {p} is not prime"));
}
let mut covered: HashSet<Vec<u64>> = HashSet::new();
for ord in orderings {
if ord.is_empty() {
return VerifyResult::fail("empty ordering (A must be nonempty)");
}
let set: HashSet<&u64> = ord.iter().collect();
if set.len() != ord.len() {
return VerifyResult::fail("ordering has a repeated element");
}
for &a in ord {
if a == 0 || a >= p {
return VerifyResult::fail(format!("element {a} not in F_{p}\\{{0}}"));
}
}
let mut seen: HashSet<u64> = HashSet::new();
let mut acc = 0u64;
for &a in ord {
acc = (acc + a) % p;
if !seen.insert(acc) {
let mut key: Vec<u64> = ord.clone();
key.sort_unstable();
return VerifyResult::fail(format!(
"subset {key:?}: ordering {ord:?} has a repeated partial sum mod {p}"
));
}
}
let mut key: Vec<u64> = ord.clone();
key.sort_unstable();
if !covered.insert(key.clone()) {
return VerifyResult::fail(format!("subset {key:?} covered more than once"));
}
}
let expected = (1u64 << (p - 1)) - 1; if covered.len() as u64 != expected {
return VerifyResult::fail(format!(
"incomplete coverage: {} of {expected} nonempty subsets of F_{p}\\{{0}}",
covered.len()
));
}
VerifyResult::ok(format!(
"Erdős #475 (distinct partial sums) verified for ALL nonempty A ⊆ F_{p}\\{{0}}: \
{expected} subsets, each orderable with distinct partial sums mod {p}. \
Finite confirmation; the question over all primes is the open problem."
))
}
pub fn verify_unit_fraction_decomp(n_max: u64, cases: &[UnitFractionCase]) -> VerifyResult {
if n_max < 3 {
return VerifyResult::fail("n_max must be >= 3 (the conjecture is stated for n > 2)");
}
let mut seen: HashSet<u64> = HashSet::new();
for c in cases {
if c.n < 3 || c.n > n_max {
return VerifyResult::fail(format!("case n={} is outside [3, {n_max}]", c.n));
}
if !seen.insert(c.n) {
return VerifyResult::fail(format!("duplicate case for n={}", c.n));
}
if !(1 <= c.x && c.x < c.y && c.y < c.z) {
return VerifyResult::fail(format!(
"n={}: triple ({},{},{}) is not 1 <= x < y < z",
c.n, c.x, c.y, c.z
));
}
let (n, x, y, z) = (c.n as u128, c.x as u128, c.y as u128, c.z as u128);
let lhs = 4u128 * x * y * z;
let rhs = n * (y * z + x * z + x * y);
if lhs != rhs {
return VerifyResult::fail(format!(
"n={}: 4/{} != 1/{}+1/{}+1/{} (exact check failed)",
c.n, c.n, c.x, c.y, c.z
));
}
}
let expected = (n_max - 3 + 1) as usize;
if seen.len() != expected {
return VerifyResult::fail(format!(
"incomplete: covered {} of {expected} values in [3, {n_max}]",
seen.len()
));
}
VerifyResult::ok(format!(
"Erdős–Straus (#242, distinct variant) verified for all 3 <= n <= {n_max}: \
{expected} exact decompositions 4/n = 1/x+1/y+1/z with x < y < z. \
Finite confirmation; the uniform proof over all n is the open problem."
))
}
pub fn verify_brocard_no_square(n_min: u64, n_max: u64, cases: &[BrocardCase]) -> VerifyResult {
if n_min < 1 || n_max < n_min {
return VerifyResult::fail("require 1 <= n_min <= n_max");
}
if n_max > 5_000_000 {
return VerifyResult::fail("n_max too large for the in-gate certificate (cap 5e6)");
}
let is_prime = |n: u64| -> bool {
if n < 2 {
return false;
}
if n.is_multiple_of(2) {
return n == 2;
}
let mut d = 3u64;
while d * d <= n {
if n.is_multiple_of(d) {
return false;
}
d += 2;
}
true
};
let mod_pow = |mut base: u128, mut exp: u128, modulus: u128| -> u128 {
if modulus == 1 {
return 0;
}
let mut result = 1u128;
base %= modulus;
while exp > 0 {
if exp & 1 == 1 {
result = result * base % modulus;
}
exp >>= 1;
base = base * base % modulus;
}
result
};
let known: [u64; 3] = [4, 5, 7];
let mut seen: HashSet<u64> = HashSet::new();
for c in cases {
if c.n < n_min || c.n > n_max {
return VerifyResult::fail(format!("case n={} outside [{n_min}, {n_max}]", c.n));
}
if !seen.insert(c.n) {
return VerifyResult::fail(format!("duplicate case for n={}", c.n));
}
if known.contains(&c.n) {
let mut fact: u128 = 1;
for k in 1..=c.n as u128 {
fact *= k;
}
let val = fact + 1;
let root = (val as f64).sqrt() as u128;
let mut is_sq = false;
for m in root.saturating_sub(2)..=root + 2 {
if m * m == val {
is_sq = true;
break;
}
}
if !is_sq {
return VerifyResult::fail(format!(
"n={}: {}!+1 = {val} is not a perfect square (expected a known solution)",
c.n, c.n
));
}
} else {
let p = c.p;
if p <= c.n {
return VerifyResult::fail(format!(
"n={}: witnessing prime p={p} must exceed n",
c.n
));
}
if !is_prime(p) {
return VerifyResult::fail(format!("n={}: p={p} is not prime", c.n));
}
let pm = p as u128;
let mut fact = 1u128;
for k in 1..=c.n {
fact = fact * (k as u128) % pm;
}
let r = (fact + 1) % pm;
if r == 0 {
return VerifyResult::fail(format!(
"n={}: n!+1 ≡ 0 (mod {p}); that does not prove a non-square",
c.n
));
}
let legendre = mod_pow(r, (pm - 1) / 2, pm);
if legendre != pm - 1 {
return VerifyResult::fail(format!(
"n={}: r={r} is a quadratic residue mod {p} \
(r^((p-1)/2) mod p = {legendre}, need {}); n!+1 not shown non-square",
c.n,
pm - 1
));
}
}
}
let expected = (n_max - n_min + 1) as usize;
if seen.len() != expected {
return VerifyResult::fail(format!(
"incomplete: covered {} of {expected} values in [{n_min}, {n_max}]",
seen.len()
));
}
let exceptions: Vec<u64> = known
.iter()
.copied()
.filter(|&n| n >= n_min && n <= n_max)
.collect();
VerifyResult::ok(format!(
"Erdős #398 (Brocard) verified for all {n_min} <= n <= {n_max}: n!+1 is a perfect \
square exactly for n in {exceptions:?}, and a non-square (quadratic-non-residue \
certificate mod a witnessing prime) for every other n. Finite confirmation; the \
conjecture over all n is the open problem."
))
}
pub fn verify_semiprime_egyptian(cases: &[SemiprimeEgyptianCase]) -> VerifyResult {
if cases.is_empty() {
return VerifyResult::fail("no cases supplied");
}
let gcd = |mut a: u64, mut b: u64| -> u64 {
while b != 0 {
let t = a % b;
a = b;
b = t;
}
a
};
let gcd128 = |mut a: u128, mut b: u128| -> u128 {
while b != 0 {
let t = a % b;
a = b;
b = t;
}
a
};
let is_squarefree_semiprime = |n: u64| -> bool {
if n < 6 {
return false;
}
let mut m = n;
let mut factors = 0u32;
let mut d = 2u64;
while d * d <= m {
if m.is_multiple_of(d) {
let mut e = 0u32;
while m.is_multiple_of(d) {
m /= d;
e += 1;
}
if e != 1 {
return false; }
factors += 1;
}
d += 1;
}
if m > 1 {
factors += 1;
}
factors == 2
};
let is_squarefree = |mut n: u64| -> bool {
let mut d = 2u64;
while d * d <= n {
if n.is_multiple_of(d) {
n /= d;
if n.is_multiple_of(d) {
return false;
}
} else {
d += 1;
}
}
true
};
let mut seen: HashSet<(u64, u64)> = HashSet::new();
for c in cases {
if c.a == 0 || c.b == 0 {
return VerifyResult::fail("a and b must be positive");
}
let g = gcd(c.a, c.b);
let (ar, br) = (c.a / g, c.b / g);
if !is_squarefree(br) {
return VerifyResult::fail(format!(
"{}/{}: reduced denominator {br} is not squarefree",
c.a, c.b
));
}
if !seen.insert((ar, br)) {
return VerifyResult::fail(format!("duplicate rational {ar}/{br}"));
}
let d = &c.denominators;
if d.is_empty() {
return VerifyResult::fail(format!("{ar}/{br}: empty denominator list"));
}
for w in d.windows(2) {
if w[0] >= w[1] {
return VerifyResult::fail(format!(
"{ar}/{br}: denominators must be strictly increasing"
));
}
}
for &ni in d {
if !is_squarefree_semiprime(ni) {
return VerifyResult::fail(format!(
"{ar}/{br}: denominator {ni} is not a product of two distinct primes"
));
}
}
let mut sn: u128 = 0;
let mut sd: u128 = 1;
for &ni in d {
let ni = ni as u128;
let nn = sn.checked_mul(ni).and_then(|v| v.checked_add(sd));
let nd = sd.checked_mul(ni);
match (nn, nd) {
(Some(nn), Some(nd)) => {
let g = gcd128(nn, nd).max(1);
sn = nn / g;
sd = nd / g;
}
_ => {
return VerifyResult::fail(format!(
"{ar}/{br}: denominator product overflow (expansion too long/large)"
));
}
}
}
let lhs = sn.checked_mul(br as u128);
let rhs = (ar as u128).checked_mul(sd);
match (lhs, rhs) {
(Some(l), Some(r)) if l == r => {}
(Some(_), Some(_)) => {
return VerifyResult::fail(format!(
"{ar}/{br}: sum of 1/n_i = {sn}/{sd} != {ar}/{br}"
));
}
_ => {
return VerifyResult::fail(format!("{ar}/{br}: overflow comparing the exact sum"));
}
}
}
VerifyResult::ok(format!(
"Erdős #306 verified: {} reduced a/b (b squarefree) each exhibited as an Egyptian \
expansion into distinct squarefree-semiprime unit fractions. Per-instance finite \
confirmation; the question over all positive rationals is the open problem.",
cases.len()
))
}
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct ParsedClaim {
pub kind: String,
pub ambient_n: Option<usize>,
pub bound: usize,
pub exact: bool,
#[serde(default, skip_serializing_if = "Option::is_none")]
pub h: Option<usize>,
#[serde(default, skip_serializing_if = "Option::is_none")]
pub d: Option<usize>,
#[serde(default, skip_serializing_if = "Option::is_none")]
pub w: Option<usize>,
}
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct Faithfulness {
pub faithful: bool,
pub reasons: Vec<String>,
#[serde(default, skip_serializing_if = "Option::is_none")]
pub parsed: Option<ParsedClaim>,
}
fn leading_usize(s: &str) -> Option<usize> {
let s = s.trim_start();
let digits: String = s.chars().take_while(|c| c.is_ascii_digit()).collect();
if digits.is_empty() {
None
} else {
digits.parse().ok()
}
}
fn usize_after_any(hay: &str, needles: &[&str]) -> Option<usize> {
let mut best: Option<(usize, usize)> = None; for needle in needles {
if let Some(idx) = hay.find(needle)
&& let Some(v) = leading_usize(&hay[idx + needle.len()..])
&& best.map(|(_, p)| idx < p).unwrap_or(true)
{
best = Some((v, idx));
}
}
best.map(|(v, _)| v)
}
fn order_in_a_paren(text: &str) -> Option<usize> {
text.find("a(").and_then(|i| leading_usize(&text[i + 2..]))
}
fn equality_bound(text: &str) -> Option<usize> {
if let Some(v) = usize_after_any(text, &["exactly "]) {
return Some(v);
}
let mut from = 0;
while let Some(rel) = text[from..].find('=') {
let idx = from + rel;
let prev = text[..idx].chars().last();
let compound = matches!(
prev,
Some('>') | Some('<') | Some('!') | Some('=') | Some('\u{2265}') | Some('\u{2264}')
);
if !compound && let Some(v) = leading_usize(&text[idx + 1..]) {
return Some(v);
}
from = idx + 1;
}
None
}
fn bh_order(text: &str) -> Option<usize> {
let subscript = text.find("b_").and_then(|i| leading_usize(&text[i + 2..]));
let fold = text.find("-fold").and_then(|i| {
let pre: String = text[..i]
.chars()
.rev()
.take_while(|c| c.is_ascii_digit())
.collect();
pre.chars().rev().collect::<String>().parse().ok()
});
match (subscript, fold) {
(Some(a), Some(b)) if a != b => None,
(Some(a), _) => Some(a),
(None, Some(b)) => Some(b),
(None, None) => None,
}
}
fn cw_params(text: &str) -> Option<(usize, usize, usize)> {
let i = text.find("a(")?;
let rest = &text[i + 2..];
let close = rest.find(')')?;
let parts: Vec<&str> = rest[..close].split(',').collect();
if parts.len() != 3 {
return None;
}
Some((
parts[0].trim().parse().ok()?,
parts[1].trim().parse().ok()?,
parts[2].trim().parse().ok()?,
))
}
pub fn parse_claim(assertion_text: &str) -> Option<ParsedClaim> {
let text = assertion_text.to_lowercase();
let kind = if text.contains("gf(2)") && text.contains("sidon") {
"gf2_sidon"
} else if text.contains("sidon") {
"sidon"
} else if text.contains("golomb") {
"golomb"
} else if text.contains("cap set") || text.contains("cap-set") {
"cap"
} else if text.contains("b_h") || text.contains("bh set") || bh_order(&text).is_some() {
"bh"
} else if text.contains("constant weight") || text.contains("constant-weight") {
"constant_weight"
} else if text.contains("union-free") || text.contains("union free") {
"union_free"
} else {
return None;
};
let order = order_in_a_paren(&text);
let literal = ["{0,1}^", "gf(2)^", "f_3^"].iter().find_map(|m| {
text.find(m)
.and_then(|i| leading_usize(&text[i + m.len()..]))
});
let ambient_n = match (order, literal) {
(Some(a), Some(b)) if a != b => return None,
(Some(a), _) => Some(a),
(None, Some(b)) => Some(b),
(None, None) => None,
};
let lower = usize_after_any(&text, &[">=", "\u{2265}", "at least "]);
let equality = equality_bound(&text);
let (bound, is_exact) = match (lower, equality) {
(Some(l), None) => (l, false),
(None, Some(e)) => (e, true),
_ => return None,
};
let h = bh_order(&text);
let (d, w) = match cw_params(&text) {
Some((_, d, w)) => (Some(d), Some(w)),
None => (None, None),
};
Some(ParsedClaim {
kind: kind.to_string(),
ambient_n,
bound,
exact: is_exact,
h,
d,
w,
})
}
pub fn claim_witness_faithful(assertion_text: &str, witness: &Witness) -> Faithfulness {
verify_witness_with_claim(assertion_text, witness).1
}
pub fn verify_witness_with_claim(
assertion_text: &str,
witness: &Witness,
) -> (VerifyResult, Faithfulness) {
let verification = verify_witness(witness);
let faithfulness =
claim_witness_faithful_from_verification(assertion_text, witness, &verification);
(verification, faithfulness)
}
fn claim_witness_faithful_from_verification(
assertion_text: &str,
witness: &Witness,
verification: &VerifyResult,
) -> Faithfulness {
let mut reasons = Vec::new();
let Some(parsed) = parse_claim(assertion_text) else {
reasons.push(
"assertion does not parse to a recognized exact-lane claim (kind keyword + a single \
unambiguous >=/exactly bound); routes to review"
.to_string(),
);
return Faithfulness {
faithful: false,
reasons,
parsed: None,
};
};
if !verification.ok {
reasons.push(format!("witness does not verify: {}", verification.message));
return Faithfulness {
faithful: false,
reasons,
parsed: Some(parsed),
};
}
if parsed.kind != witness.kind() {
reasons.push(format!(
"claim kind '{}' does not match witness kind '{}'",
parsed.kind,
witness.kind()
));
return Faithfulness {
faithful: false,
reasons,
parsed: Some(parsed),
};
}
if parsed.exact {
reasons.push(
"equality/optimality claim (= / exactly) is not establishable by a construction \
witness (which proves only a lower bound); routes to review"
.to_string(),
);
return Faithfulness {
faithful: false,
reasons,
parsed: Some(parsed),
};
}
let dim_n_witness = |n: usize| -> Option<String> {
match parsed.ambient_n {
None => Some(
"dimensioned claim states no ambient dimension (a(N) / {0,1}^N / gf(2)^N); \
routes to review"
.to_string(),
),
Some(c) if c != n => Some(format!(
"claim ambient dimension n={c} does not match witness n={n}"
)),
Some(_) => None,
}
};
let size: usize = match witness {
Witness::Sidon { n, points, .. } | Witness::Cap { n, points, .. } => {
if let Some(r) = dim_n_witness(*n) {
reasons.push(r);
return Faithfulness {
faithful: false,
reasons,
parsed: Some(parsed),
};
}
points.len()
}
Witness::UnionFree { n, sets, .. } => {
if let Some(r) = dim_n_witness(*n) {
reasons.push(r);
return Faithfulness {
faithful: false,
reasons,
parsed: Some(parsed),
};
}
sets.len()
}
Witness::Gf2Sidon { elements, .. } => {
let Some(claim_n) = parsed.ambient_n else {
reasons.push(
"GF(2)-Sidon claim states no dimension N (a(N) / gf(2)^N); routes to review"
.to_string(),
);
return Faithfulness {
faithful: false,
reasons,
parsed: Some(parsed),
};
};
if claim_n >= 64 || elements.iter().any(|e| (*e >> claim_n) != 0) {
reasons.push(format!(
"witness has an element outside GF(2)^{claim_n}; it does not establish a(N) \
at that dimension"
));
return Faithfulness {
faithful: false,
reasons,
parsed: Some(parsed),
};
}
elements.len()
}
Witness::Bh { n, h, points, .. } => {
if let Some(r) = dim_n_witness(*n) {
reasons.push(r);
return Faithfulness {
faithful: false,
reasons,
parsed: Some(parsed),
};
}
match parsed.h {
Some(ch) if ch == *h => {}
Some(ch) => {
reasons.push(format!(
"claim B_{ch} does not match witness B_{h} (the order h binds the record)"
));
return Faithfulness {
faithful: false,
reasons,
parsed: Some(parsed),
};
}
None => {
reasons.push(
"B_h claim does not state the order h (B_<h> / <h>-fold); routes to review"
.to_string(),
);
return Faithfulness {
faithful: false,
reasons,
parsed: Some(parsed),
};
}
}
points.len()
}
Witness::ConstantWeight { n, d, w, words, .. } => {
if let Some(r) = dim_n_witness(*n) {
reasons.push(r);
return Faithfulness {
faithful: false,
reasons,
parsed: Some(parsed),
};
}
match (parsed.d, parsed.w) {
(Some(cd), Some(cw)) if cd == *d && cw == *w => {}
(Some(cd), Some(cw)) => {
reasons.push(format!(
"claim A(n,{cd},{cw}) does not match witness A(n,{d},{w}) (d,w bind the record)"
));
return Faithfulness {
faithful: false,
reasons,
parsed: Some(parsed),
};
}
_ => {
reasons.push(
"constant-weight claim does not state (d,w) as A(n,d,w); routes to review"
.to_string(),
);
return Faithfulness {
faithful: false,
reasons,
parsed: Some(parsed),
};
}
}
words.len()
}
Witness::Golomb { .. } => {
reasons.push(
"golomb claims are not floor-admissible (no sound witness->bound binding \
defined); routes to review"
.to_string(),
);
return Faithfulness {
faithful: false,
reasons,
parsed: Some(parsed),
};
}
_ => {
reasons.push(format!(
"witness kind '{}' is not an exact-lane size/order claim",
witness.kind()
));
return Faithfulness {
faithful: false,
reasons,
parsed: Some(parsed),
};
}
};
if size < parsed.bound {
reasons.push(format!(
"witness size/order {size} does not establish the claimed >= {}",
parsed.bound
));
return Faithfulness {
faithful: false,
reasons,
parsed: Some(parsed),
};
}
Faithfulness {
faithful: true,
reasons,
parsed: Some(parsed),
}
}
pub fn canonical_claim(witness: &Witness) -> Option<String> {
match witness {
Witness::Sidon { n, points, .. } => Some(format!(
"Sidon set: a({n}) >= {} (a Sidon set of {} points in {{0,1}}^{n})",
points.len(),
points.len()
)),
Witness::Cap { n, points, .. } => Some(format!(
"cap set: a({n}) >= {} (a cap set of {} points in F_3^{n})",
points.len(),
points.len()
)),
Witness::Gf2Sidon { elements, .. } => {
let n = elements
.iter()
.map(|e| (64 - e.leading_zeros()) as usize)
.max()
.unwrap_or(0);
Some(format!(
"GF(2)-Sidon set: a({n}) >= {} (a Sidon set of {} elements in GF(2)^{n})",
elements.len(),
elements.len()
))
}
Witness::UnionFree { n, sets, .. } => Some(format!(
"union-free family: a({n}) >= {} (a union-free family of {} subsets of {{1..{n}}})",
sets.len(),
sets.len()
)),
Witness::Bh { n, h, points, .. } => Some(format!(
"B_{h} set: a({n}) >= {} (a B_{h} set of {} points in {{0,1}}^{n})",
points.len(),
points.len()
)),
Witness::ConstantWeight { n, d, w, words, .. } => Some(format!(
"constant-weight code: A({n},{d},{w}) >= {} ({} codewords of length {n}, weight {w}, min distance {d})",
words.len(),
words.len()
)),
_ => None,
}
}
fn with_size(mut r: VerifyResult, actual: usize, claimed: Option<usize>) -> VerifyResult {
if r.ok
&& let Some(c) = claimed
{
if actual != c {
return VerifyResult::fail(format!(
"verifier passed but construction size {actual} != claimed_size {c}"
));
}
r.message = format!("{} (size {actual} = claimed)", r.message);
}
r
}
fn binary_points_ok(points: &[Vec<i64>], n: usize) -> Option<VerifyResult> {
let set: HashSet<&Vec<i64>> = points.iter().collect();
if set.len() != points.len() {
return Some(VerifyResult::fail("duplicate points"));
}
if !points
.iter()
.all(|p| p.len() == n && p.iter().all(|&x| x == 0 || x == 1))
{
return Some(VerifyResult::fail(format!("points not binary length-{n}")));
}
None
}
pub fn verify_sidon(points: &[Vec<i64>], n: usize) -> VerifyResult {
if let Some(bad) = binary_points_ok(points, n) {
return bad;
}
let m = points.len();
if n <= 32 {
let Some(pair_count) = m
.checked_add(1)
.and_then(|next| m.checked_mul(next))
.map(|value| value / 2)
else {
return VerifyResult::fail("pairwise-sum count overflows this platform");
};
let expanded = points
.iter()
.map(|point| {
point
.iter()
.enumerate()
.fold(0_u64, |packed, (index, value)| {
packed | ((*value as u64) << (2 * index))
})
})
.collect::<Vec<_>>();
let mut sums = Vec::new();
if sums.try_reserve_exact(pair_count).is_err() {
return VerifyResult::fail("insufficient memory for pairwise-sum check");
}
for i in 0..m {
for j in i..m {
sums.push(expanded[i] + expanded[j]);
}
}
sums.sort_unstable();
if sums.windows(2).any(|pair| pair[0] == pair[1]) {
return VerifyResult::fail("pairwise-sum collision (not Sidon)");
}
return VerifyResult::ok(format!(
"Sidon verified: {m} points, {pair_count} pairwise sums all distinct"
));
}
let mut sums: HashSet<Vec<i64>> = HashSet::new();
let mut count = 0usize;
for i in 0..m {
for j in i..m {
let s: Vec<i64> = (0..n).map(|k| points[i][k] + points[j][k]).collect();
if !sums.insert(s) {
return VerifyResult::fail("pairwise-sum collision (not Sidon)");
}
count += 1;
}
}
VerifyResult::ok(format!(
"Sidon verified: {m} points, {count} pairwise sums all distinct"
))
}
#[must_use]
pub fn verify_gf2_sidon(elements: &[u64]) -> VerifyResult {
let m = elements.len();
let distinct: HashSet<u64> = elements.iter().copied().collect();
if distinct.len() != m {
return VerifyResult::fail("duplicate element (not a set)");
}
let mut xors: HashSet<u64> = HashSet::new();
let mut count = 0usize;
for i in 0..m {
for j in (i + 1)..m {
let x = elements[i] ^ elements[j];
if x == 0 {
return VerifyResult::fail("zero XOR (equal elements)");
}
if !xors.insert(x) {
return VerifyResult::fail("pairwise-XOR collision (not a GF(2) Sidon set)");
}
count += 1;
}
}
VerifyResult::ok(format!(
"GF(2)-Sidon verified: {m} elements, {count} pairwise XORs all distinct"
))
}
fn gcd_pos(a: i64, b: i64) -> i64 {
let (mut a, mut b) = (a.abs(), b.abs());
while b != 0 {
let t = b;
b = a % b;
a = t;
}
if a == 0 { 1 } else { a }
}
#[must_use]
pub fn verify_union_free(n: usize, sets: &[Vec<u32>]) -> VerifyResult {
if n == 0 || n > 63 {
return VerifyResult::fail("n out of range (1..=63)");
}
let mut masks: Vec<u64> = Vec::with_capacity(sets.len());
for s in sets {
if s.is_empty() {
return VerifyResult::fail("empty set (members must be nonempty)");
}
let mut m = 0u64;
for &e in s {
if e < 1 || (e as usize) > n {
return VerifyResult::fail(format!("element {e} out of {{1..{n}}}"));
}
m |= 1u64 << (e - 1);
}
masks.push(m);
}
let distinct: HashSet<u64> = masks.iter().copied().collect();
if distinct.len() != masks.len() {
return VerifyResult::fail("duplicate set (members must be distinct)");
}
for (i, &c) in masks.iter().enumerate() {
let mut u = 0u64;
for (j, &s) in masks.iter().enumerate() {
if i != j && (s & c) == s {
u |= s;
}
}
if u == c {
return VerifyResult::fail(
"a member is the union of a sub-collection of the others (not union-free)",
);
}
}
VerifyResult::ok(format!(
"union-free verified: {} sets over {{1..{n}}}, no member is a union of others",
masks.len()
))
}
#[must_use]
pub fn verify_rook_directions(n: usize, perm: &[i64], claimed: Option<usize>) -> VerifyResult {
if perm.len() != n {
return VerifyResult::fail("perm length != n");
}
let mut seen = vec![false; n + 1];
for &c in perm {
if c < 1 || (c as usize) > n {
return VerifyResult::fail("column out of 1..=n");
}
if seen[c as usize] {
return VerifyResult::fail("repeated column (attacking rooks)");
}
seen[c as usize] = true;
}
let mut classes: HashSet<(i64, i64)> = HashSet::new();
for i in 0..n {
for j in (i + 1)..n {
let drow = (j as i64) - (i as i64);
let dcol = perm[j] - perm[i];
let g = gcd_pos(dcol, drow);
let (a, b) = (dcol.abs() / g, drow.abs() / g);
classes.insert(if a <= b { (a, b) } else { (b, a) });
}
}
let count = classes.len();
if let Some(cl) = claimed
&& count != cl
{
return VerifyResult::fail(format!("direction count {count} != claimed {cl}"));
}
VerifyResult::ok(format!(
"rook-directions verified: {n} non-attacking rooks realize {count} distinct direction classes"
))
}
pub fn verify_balanced_coloring(
n: usize,
r: usize,
edge_colors: &std::collections::BTreeMap<String, u32>,
) -> VerifyResult {
if r < 2 || n < r + 1 {
return VerifyResult::fail(format!("need r >= 2 and n >= r+1 (got n={n}, r={r})"));
}
let mut color = vec![vec![0u32; n]; n];
for (key, &c) in edge_colors {
let Some((a, b)) = key.split_once(',') else {
return VerifyResult::fail(format!("bad edge key '{key}' (want \"i,j\")"));
};
let (Ok(i), Ok(j)) = (a.trim().parse::<usize>(), b.trim().parse::<usize>()) else {
return VerifyResult::fail(format!("bad edge key '{key}'"));
};
if i >= n || j >= n || i >= j {
return VerifyResult::fail(format!("edge '{key}' out of range or not i<j for n={n}"));
}
if c == 0 || c as usize > r {
return VerifyResult::fail(format!("edge '{key}' color {c} outside 1..={r}"));
}
color[i][j] = c;
}
for (i, row) in color.iter().enumerate() {
for (j, &c) in row.iter().enumerate().skip(i + 1) {
if c == 0 {
return VerifyResult::fail(format!("edge {i},{j} is uncolored"));
}
}
}
let k = r + 1;
let mut idx: Vec<usize> = (0..k).collect();
let mut checked = 0u64;
loop {
let mut seen = vec![false; r + 1];
for x in 0..k {
for y in (x + 1)..k {
seen[color[idx[x]][idx[y]] as usize] = true;
}
}
if let Some(missing) = (1..=r).find(|&c| !seen[c]) {
return VerifyResult::fail(format!("subset {:?} sees no edge of color {missing}", idx));
}
checked += 1;
let mut pos = k;
while pos > 0 {
pos -= 1;
if idx[pos] != pos + n - k {
idx[pos] += 1;
for q in (pos + 1)..k {
idx[q] = idx[q - 1] + 1;
}
break;
}
if pos == 0 {
return VerifyResult::ok(format!(
"balanced {r}-coloring of K_{n} verified: {checked} {k}-subsets each see all {r} colors"
));
}
}
}
}
pub fn verify_interval_product(p: u64, cuts: &[u64]) -> VerifyResult {
if !is_prime(p) {
return VerifyResult::fail(format!("modulus p={p} must be prime"));
}
if cuts.len() < 2 {
return VerifyResult::fail("need at least two cuts (one interval)");
}
for w in cuts.windows(2) {
if w[0] >= w[1] {
return VerifyResult::fail("cuts must be strictly increasing");
}
}
for w in cuts.windows(2) {
let mut prod: u64 = 1;
for m in (w[0] + 1)..=w[1] {
prod = ((prod as u128 * (m % p) as u128) % p as u128) as u64;
}
if prod != 1 {
return VerifyResult::fail(format!(
"interval ({}, {}] has product {prod} mod {p} != 1",
w[0], w[1]
));
}
}
VerifyResult::ok(format!(
"Erdos #1056 certificate: prime p={p}, {} consecutive interval(s) each with product 1 mod p",
cuts.len() - 1
))
}
fn carries_base_p(mut a: u128, mut b: u128, p: u128) -> u64 {
let mut carry: u128 = 0;
let mut count: u64 = 0;
while a > 0 || b > 0 || carry > 0 {
let s = a % p + b % p + carry;
carry = u128::from(s >= p);
count += carry as u64;
a /= p;
b /= p;
}
count
}
fn vp_factorial(n: u64, p: u64) -> u64 {
let mut s = 0u64;
let mut pk = p;
while pk <= n {
s += n / pk;
pk = pk.saturating_mul(p);
}
s
}
fn vp_binom(n: u64, k: u64, p: u64) -> u64 {
vp_factorial(n, p) - vp_factorial(k, p) - vp_factorial(n - k, p)
}
fn vp_of(mut n: u64, p: u64) -> u64 {
let mut v = 0u64;
while n.is_multiple_of(p) {
n /= p;
v += 1;
}
v
}
fn gcd_u64(mut a: u64, mut b: u64) -> u64 {
while b != 0 {
let t = a % b;
a = b;
b = t;
}
a
}
fn primes_upto(n: u64) -> Vec<u64> {
(2..=n).filter(|&q| is_prime(q)).collect()
}
fn parse_decimal_u128(s: &str) -> Result<u128, String> {
if s.is_empty() || s.len() > 38 || !s.bytes().all(|b| b.is_ascii_digit()) {
return Err(format!("`{s}` is not a 1..=38 digit decimal string"));
}
s.parse::<u128>().map_err(|e| format!("parse `{s}`: {e}"))
}
fn decimal_mod(s: &str, m: u64) -> Result<u64, String> {
if s.is_empty() || !s.bytes().all(|b| b.is_ascii_digit()) {
return Err(format!("`{s}` is not a decimal string"));
}
let mut acc: u64 = 0;
for b in s.bytes() {
acc = (acc * 10 + u64::from(b - b'0')) % m;
}
Ok(acc)
}
fn multiplicative_order(base: u64, p: u64) -> Result<u64, String> {
if base.is_multiple_of(p) {
return Err(format!("{base} is 0 mod {p}; order undefined"));
}
let mut acc = base % p;
let mut ord = 1u64;
while acc != 1 {
acc = acc * base % p;
ord += 1;
if ord >= p {
return Err(format!("order of {base} mod {p} did not divide p-1"));
}
}
Ok(ord)
}
pub fn verify_crt_partial_cover(m: &str, rows: &[CrtCoverRow]) -> VerifyResult {
if rows.is_empty() {
return VerifyResult::fail("need at least one prime row");
}
match (decimal_mod(m, 2), decimal_mod(m, 3)) {
(Ok(r2), Ok(r3)) => {
if r2 == 0 || r3 == 0 {
return VerifyResult::fail("m must be coprime to 6");
}
}
(Err(e), _) | (_, Err(e)) => return VerifyResult::fail(e),
}
for row in rows {
let p = row.p;
if !(5..=1_000_000).contains(&p) || !is_prime(p) {
return VerifyResult::fail(format!("row p={p} must be a prime in [5, 10^6]"));
}
let ord2 = match multiplicative_order(2, p) {
Ok(v) => v,
Err(e) => return VerifyResult::fail(e),
};
let ord3 = match multiplicative_order(3, p) {
Ok(v) => v,
Err(e) => return VerifyResult::fail(e),
};
if ord2 != row.ord2 || ord3 != row.ord3 {
return VerifyResult::fail(format!(
"row p={p}: ord(2)={ord2}, ord(3)={ord3} != claimed ({}, {})",
row.ord2, row.ord3
));
}
let h = ord2 / gcd_u64(ord2, ord3) * ord3;
if h != row.h || row.line[3] != h {
return VerifyResult::fail(format!(
"row p={p}: lcm(ord2, ord3)={h} != claimed h={} / line modulus {}",
row.h, row.line[3]
));
}
if h > 5_000 {
return VerifyResult::fail(format!("row p={p}: h={h} exceeds the 5000 guard"));
}
let mm = match decimal_mod(m, p) {
Ok(v) => v,
Err(e) => return VerifyResult::fail(e),
};
if mm != row.m_mod_p || mm == 0 {
return VerifyResult::fail(format!(
"row p={p}: m mod p = {mm} != claimed {} (and must be nonzero)",
row.m_mod_p
));
}
let t = (p - mod_pow(mm, p - 2, p)) % p;
if t != row.t_p {
return VerifyResult::fail(format!(
"row p={p}: (-m^-1) mod p = {t} != claimed t_p={}",
row.t_p
));
}
let (al, be, ga) = (row.line[0], row.line[1], row.line[2]);
for k in 0..h {
for l in 0..h {
let lhs = (mod_pow(2, k, p) * mod_pow(3, l, p) % p * mm % p + 1).is_multiple_of(p);
let rhs = (al * k + be * l) % h == ga % h; if lhs != rhs {
return VerifyResult::fail(format!(
"row p={p}: congruence line fails at (k, l) = ({k}, {l})"
));
}
}
}
}
VerifyResult::ok(format!(
"Erdos #203 partial CRT cover: m coprime to 6, {} prime row(s) verified (p | 2^k 3^l m + 1 <=> affine line mod h)",
rows.len()
))
}
pub fn verify_kummer_no_carry(entries: &[KummerEntry]) -> VerifyResult {
if entries.is_empty() {
return VerifyResult::fail("need at least one (k, m) entry");
}
for e in entries {
let k = e.k;
if !(3..=20).contains(&k) {
return VerifyResult::fail(format!("k={k} outside the [3, 20] guard"));
}
let mut m: u64 = 1;
for p in primes_upto(k) {
let mut pe = 1u64;
let mut exp = 0u64;
while pe * p <= k {
pe *= p;
exp += 1;
}
for _ in 0..=exp {
m = match m.checked_mul(p) {
Some(v) => v,
None => return VerifyResult::fail(format!("M_{k} overflows u64")),
};
}
}
if m != e.m {
return VerifyResult::fail(format!("k={k}: recomputed M_k={m} != claimed {}", e.m));
}
let n = m - 1;
for j in 2..=k {
for p in primes_upto(j) {
if carries_base_p(u128::from(j), u128::from(n - j), u128::from(p)) != 0 {
return VerifyResult::fail(format!(
"k={k}: carry adding {j} + (M-1-{j}) base {p} — C(M-1, {j}) not p-free"
));
}
}
}
}
VerifyResult::ok(format!(
"Erdos #684 certificate: f(M_k - 1) > k verified for {} value(s) of k (zero Kummer carries)",
entries.len()
))
}
pub fn verify_min_binom_gcd(cases: &[MinGcdCase]) -> VerifyResult {
if cases.is_empty() {
return VerifyResult::fail("need at least one (n, f) case");
}
for c in cases {
let n = c.n;
if !(4..=10_000).contains(&n) {
return VerifyResult::fail(format!("n={n} outside the [4, 10000] guard"));
}
let mut factors: Vec<(u64, u64)> = Vec::new();
let mut rem = n;
let mut p = 2u64;
while p * p <= rem {
if rem.is_multiple_of(p) {
factors.push((p, vp_of(rem, p)));
while rem.is_multiple_of(p) {
rem /= p;
}
}
p += 1;
}
if rem > 1 {
factors.push((rem, 1));
}
let mut best = u64::MAX;
for k in 2..=n / 2 {
let mut g = 1u64;
for &(p, vn) in &factors {
let carries = carries_base_p(u128::from(k), u128::from(n - k), u128::from(p));
g *= p.pow(vn.min(carries) as u32);
}
best = best.min(g);
}
if best != c.f {
return VerifyResult::fail(format!("n={n}: recomputed f(n)={best} != claimed {}", c.f));
}
}
VerifyResult::ok(format!(
"Erdos #700 certificate: f(n) = min gcd(n, C(n,k)) verified for {} case(s)",
cases.len()
))
}
fn divides_smooth(mut x: u128, i: u64, k: u64) -> bool {
for p in primes_upto(k) {
if x == 1 {
break;
}
let pp = u128::from(p);
let mut e = 0u64;
while x.is_multiple_of(pp) {
x /= pp;
e += 1;
}
if e > 0 && vp_of(i, p) + vp_binom(k, i, p) < e {
return false;
}
}
x == 1
}
pub fn verify_binom_deficiency(entries: &[DeficiencyEntry]) -> VerifyResult {
if entries.is_empty() {
return VerifyResult::fail("need at least one entry");
}
for e in entries {
let k = e.k;
if !(2..=150).contains(&k) {
return VerifyResult::fail(format!("k={k} outside the [2, 150] guard"));
}
let n = match parse_decimal_u128(&e.n) {
Ok(v) => v,
Err(err) => return VerifyResult::fail(err),
};
if n < 2 * u128::from(k) {
return VerifyResult::fail(format!("entry k={k}: need N >= 2k"));
}
for p in primes_upto(k) {
if carries_base_p(u128::from(k), n - u128::from(k), u128::from(p)) != 0 {
return VerifyResult::fail(format!(
"entry k={k}: prime {p} divides C(N,k) — not Kummer-defined"
));
}
}
let mut slots: Vec<u64> = Vec::new();
for i in 1..=k {
let x = n - u128::from(k) + u128::from(i);
if divides_smooth(x, i, k) {
slots.push(i);
}
}
if slots.len() as u64 != e.delta {
return VerifyResult::fail(format!(
"entry k={k}: recomputed delta={} != claimed {}",
slots.len(),
e.delta
));
}
if let Some(claimed) = &e.slots
&& &slots != claimed
{
return VerifyResult::fail(format!(
"entry k={k}: smooth slots {slots:?} != claimed {claimed:?}"
));
}
}
VerifyResult::ok(format!(
"Erdos #1093 deficiency certificate: {} entr(ies) Kummer-defined with delta and slots recomputed exactly",
entries.len()
))
}
fn binom_u64(k: u64, r: u64) -> u64 {
let r = r.min(k - r);
let mut res = 1u64;
for i in 1..=r {
res = res * (k - r + i) / i;
}
res
}
fn divisors_smooth(g: u64, k: u64) -> Option<Vec<u64>> {
let mut rem = g;
let mut pf: Vec<(u64, u64)> = Vec::new();
for p in primes_upto(k) {
if rem.is_multiple_of(p) {
pf.push((p, vp_of(rem, p)));
while rem.is_multiple_of(p) {
rem /= p;
}
}
}
if rem != 1 {
return None;
}
let mut divs: Vec<u64> = vec![1];
for (p, e) in pf {
let prev = divs.clone();
let mut pe = 1u64;
for _ in 0..e {
pe *= p;
for d in &prev {
divs.push(d * pe);
}
}
if divs.len() > 200_000 {
return None;
}
}
Some(divs)
}
fn is_exception_guarded(n: u64, k: u64) -> Option<bool> {
let mut p = 2u64;
while p <= k || p.saturating_mul(k) <= n {
if is_prime(p) && vp_binom(n, k, p) > 0 {
return Some(false);
}
if p > 10_000_000 {
return None;
}
p += 1;
}
Some(true)
}
pub fn verify_binom_exception_enum(k_max: u64, exceptions: &[(u64, u64)]) -> VerifyResult {
if !(3..=40).contains(&k_max) {
return VerifyResult::fail(format!("k_max={k_max} outside the [3, 40] guard"));
}
let claimed: std::collections::BTreeSet<(u64, u64)> = exceptions.iter().copied().collect();
for &(n, k) in &claimed {
if k > k_max || n < 2 * k {
return VerifyResult::fail(format!(
"claimed exception (N={n}, k={k}) outside k <= k_max / N >= 2k"
));
}
}
let mut found: std::collections::BTreeSet<(u64, u64)> = std::collections::BTreeSet::new();
let mut lambda: u64 = 1;
let mut candidates: u64 = 0;
for k in 2..=k_max {
lambda = lambda / gcd_u64(lambda, k) * k;
for r in 1..=k {
let g = gcd_u64(lambda, r * binom_u64(k, r));
let divs = match divisors_smooth(g, k) {
Some(d) => d,
None => {
return VerifyResult::fail(format!(
"divisor enumeration guard exceeded at k={k}, r={r}"
));
}
};
for x in divs {
if !x.is_multiple_of(k) {
continue;
}
let n = x + k - r;
if n < 2 * k {
continue;
}
candidates += 1;
match is_exception_guarded(n, k) {
Some(true) => {
found.insert((n, k));
}
Some(false) => {}
None => {
return VerifyResult::fail(format!(
"exception test guard exceeded at (N={n}, k={k}) — refusing to claim"
));
}
}
}
}
}
if found != claimed {
let extra: Vec<_> = found.difference(&claimed).collect();
let missing: Vec<_> = claimed.difference(&found).collect();
return VerifyResult::fail(format!(
"exception set mismatch: extra {extra:?}, missing {missing:?}"
));
}
VerifyResult::ok(format!(
"Erdos #1094 enumeration: {candidates} candidate(s) checked for k <= {k_max}; exception set of {} matches exactly",
claimed.len()
))
}
fn rat_check(step: &LratStep, db: &std::collections::HashMap<u64, Vec<i64>>) -> bool {
let Some(&pivot) = step.literals.first() else {
return false; };
let supplied: std::collections::HashMap<u64, &Vec<u64>> =
step.rat_hints.iter().map(|(id, h)| (*id, h)).collect();
for (&cid, clause) in db {
if !clause.contains(&-pivot) {
continue;
}
let mut resolvent: Vec<i64> = step.literals.clone();
for &l in clause {
if l != -pivot && l != 0 && !resolvent.contains(&l) {
resolvent.push(l);
}
}
if resolvent.iter().any(|&l| resolvent.contains(&-l) && l > 0) {
continue; }
let Some(hints) = supplied.get(&cid) else {
return false;
};
if !rup_checks(&resolvent, hints, db) {
return false;
}
}
true
}
fn rup_checks(c: &[i64], hints: &[u64], db: &std::collections::HashMap<u64, Vec<i64>>) -> bool {
let mut assign: std::collections::HashMap<i64, bool> = std::collections::HashMap::new();
for &l in c {
if l == 0 {
return false;
}
let v = l.abs();
let want = l < 0; if let Some(&prev) = assign.get(&v)
&& prev != want
{
return false; }
assign.insert(v, want);
}
for &h in hints {
let Some(cl) = db.get(&h) else {
return false; };
let mut unassigned: Vec<i64> = Vec::new();
let mut satisfied = false;
for &l in cl {
if l == 0 {
continue;
}
match assign.get(&l.abs()) {
None => unassigned.push(l),
Some(&val) => {
if (l > 0) == val {
satisfied = true;
}
}
}
}
if satisfied {
return false; }
match unassigned.len() {
0 => return true, 1 => {
let l = unassigned[0];
assign.insert(l.abs(), l > 0); }
_ => return false, }
}
false }
pub fn verify_unsat_cert(cnf: &[Vec<i64>], proof: &[LratStep]) -> VerifyResult {
if cnf.is_empty() {
return VerifyResult::fail("empty CNF: nothing to refute");
}
if cnf.len() > 5_000_000 || proof.len() > 20_000_000 {
return VerifyResult::fail("certificate exceeds the size guard");
}
let mut db: std::collections::HashMap<u64, Vec<i64>> = std::collections::HashMap::new();
for (i, clause) in cnf.iter().enumerate() {
let id = (i + 1) as u64; if db.insert(id, clause.clone()).is_some() {
return VerifyResult::fail(format!("duplicate clause id {id}"));
}
}
let mut derived_empty = false;
for step in proof {
if step.id == 0 {
return VerifyResult::fail("proof clause id 0 is reserved");
}
if !rup_checks(&step.literals, &step.hints, &db) && !rat_check(step, &db) {
return VerifyResult::fail(format!(
"LRAT step {} is neither RUP-implied nor RAT on its first literal",
step.id
));
}
let empty = step.literals.is_empty();
if db.insert(step.id, step.literals.clone()).is_some() {
return VerifyResult::fail(format!("clause id {} added twice", step.id));
}
if empty {
derived_empty = true;
break;
}
}
if !derived_empty {
return VerifyResult::fail("proof never derives the empty clause (UNSAT not established)");
}
VerifyResult::ok(format!(
"UNSAT certificate: {} clause(s), {} LRAT step(s), empty clause derived by RUP",
cnf.len(),
proof.len()
))
}
pub fn verify_golomb(marks: &[i64]) -> VerifyResult {
let set: HashSet<&i64> = marks.iter().collect();
if set.len() != marks.len() {
return VerifyResult::fail("duplicate marks");
}
let mut diffs: HashSet<i64> = HashSet::new();
let mut count = 0usize;
for i in 0..marks.len() {
for j in (i + 1)..marks.len() {
if !diffs.insert((marks[j] - marks[i]).abs()) {
return VerifyResult::fail("repeated pairwise difference (not a Golomb ruler)");
}
count += 1;
}
}
let (lo, hi) = (marks.iter().min().copied(), marks.iter().max().copied());
let length = match (lo, hi) {
(Some(a), Some(b)) => b - a,
_ => 0,
};
VerifyResult::ok(format!(
"Golomb ruler: {} marks, length {length}, all {count} differences distinct",
marks.len()
))
}
pub fn verify_cap(points: &[Vec<i64>], n: usize) -> VerifyResult {
let set: HashSet<&Vec<i64>> = points.iter().collect();
if set.len() != points.len() {
return VerifyResult::fail("duplicate points");
}
if !points
.iter()
.all(|p| p.len() == n && p.iter().all(|&x| (0..=2).contains(&x)))
{
return VerifyResult::fail(format!("points not in (0,1,2)^{n}"));
}
let owned: HashSet<Vec<i64>> = points.iter().cloned().collect();
let m = points.len();
for i in 0..m {
let a = &points[i];
for b in points.iter().take(m).skip(i + 1) {
let c: Vec<i64> = (0..n).map(|k| (-(a[k] + b[k])).rem_euclid(3)).collect();
if owned.contains(&c) && &c != a && &c != b {
return VerifyResult::fail("3 collinear points found (not a cap)");
}
}
}
VerifyResult::ok(format!(
"cap verified: {m} points in F_3^{n}, no 3 collinear"
))
}
pub fn verify_bh(points: &[Vec<i64>], n: usize, h: usize) -> VerifyResult {
if let Some(bad) = binary_points_ok(points, n) {
return bad;
}
let m = points.len();
if m == 0 || h == 0 {
return VerifyResult::ok(format!("B_{h} verified: {m} points, 0 sums"));
}
let mut sums: HashSet<Vec<i64>> = HashSet::new();
let mut count = 0usize;
let mut idx = vec![0usize; h];
loop {
let mut s = vec![0i64; n];
for &i in &idx {
for k in 0..n {
s[k] += points[i][k];
}
}
if !sums.insert(s) {
return VerifyResult::fail(format!("B_{h} violated: a repeated {h}-fold sum"));
}
count += 1;
if !advance_with_replacement(&mut idx, m) {
break;
}
}
VerifyResult::ok(format!(
"B_{h} verified: {m} points, {count} h-fold sums all distinct"
))
}
pub fn verify_covering(blocks: &[Vec<usize>], v: usize, k: usize, t: usize) -> VerifyResult {
let norm: Vec<Vec<usize>> = blocks
.iter()
.map(|b| {
let s: std::collections::BTreeSet<usize> = b.iter().copied().collect();
s.into_iter().collect()
})
.collect();
if !norm
.iter()
.all(|b| b.len() == k && b.iter().all(|&x| x < v))
{
return VerifyResult::fail(format!("blocks not valid {k}-subsets of [0,{v})"));
}
let mut covered: HashSet<Vec<usize>> = HashSet::new();
for b in &norm {
each_combination(b.len(), t, &mut |sub| {
covered.insert(sub.iter().map(|&i| b[i]).collect());
});
}
let mut need = 0usize;
let mut missing = 0usize;
each_combination(v, t, &mut |sub| {
need += 1;
if !covered.contains(sub) {
missing += 1;
}
});
if missing > 0 {
return VerifyResult::fail(format!(
"not a covering: {missing} of {need} t-subsets uncovered"
));
}
VerifyResult::ok(format!(
"valid C({v},{k},{t}) covering with {} blocks",
norm.len()
))
}
pub fn verify_constant_weight(words: &[Vec<i64>], n: usize, d: usize, w: usize) -> VerifyResult {
let set: HashSet<&Vec<i64>> = words.iter().collect();
if set.len() != words.len() {
return VerifyResult::fail("duplicate codewords");
}
if !words
.iter()
.all(|c| c.len() == n && c.iter().all(|&x| x == 0 || x == 1))
{
return VerifyResult::fail(format!("words not binary length-{n}"));
}
if let Some(c) = words.iter().find(|c| c.iter().sum::<i64>() as usize != w) {
return VerifyResult::fail(format!(
"a codeword has weight {} != {w}",
c.iter().sum::<i64>()
));
}
for i in 0..words.len() {
for j in (i + 1)..words.len() {
let dist = (0..n).filter(|&k| words[i][k] != words[j][k]).count();
if dist < d {
return VerifyResult::fail(format!("a pair has Hamming distance {dist} < {d}"));
}
}
}
VerifyResult::ok(format!(
"constant-weight code A({n},{d},{w}): {} words, all weight {w}, min dist >= {d}",
words.len()
))
}
pub fn verify_costas(perm: &[i64]) -> VerifyResult {
let n = perm.len();
let mut sorted = perm.to_vec();
sorted.sort_unstable();
let min = perm.iter().min().copied().unwrap_or(0);
let expected: Vec<i64> = (0..n as i64).map(|i| min + i).collect();
if sorted != expected {
return VerifyResult::fail("not a permutation");
}
let mut vecs: HashSet<(i64, i64)> = HashSet::new();
let mut count = 0usize;
for i in 0..n {
for j in (i + 1)..n {
if !vecs.insert(((j - i) as i64, perm[j] - perm[i])) {
return VerifyResult::fail("repeated displacement vector (not a Costas array)");
}
count += 1;
}
}
VerifyResult::ok(format!(
"Costas array of order {n} verified ({count} displacement vectors all distinct)"
))
}
#[allow(clippy::needless_range_loop)]
pub fn verify_linear_code(generator: &[Vec<i64>], q: u64, claimed_d: usize) -> VerifyResult {
const MAX_ENUM: u64 = 1_000_000;
if !is_prime(q) {
return VerifyResult::fail(format!(
"q={q} not prime; prime-power GF(q) not implemented — refusing to claim"
));
}
let k = generator.len();
if k == 0 {
return VerifyResult::fail("empty generator");
}
let n = generator[0].len();
if !generator.iter().all(|row| row.len() == n) {
return VerifyResult::fail("ragged generator matrix");
}
let g: Vec<Vec<u64>> = generator
.iter()
.map(|row| row.iter().map(|&x| x.rem_euclid(q as i64) as u64).collect())
.collect();
if gf_rank(&g, q) != k {
return VerifyResult::fail(format!(
"generator rank < k={k} (rows dependent — not an [n,{k}] code)"
));
}
let qk = (q).checked_pow(k as u32);
match qk {
Some(v) if v <= MAX_ENUM => {}
_ => {
return VerifyResult::fail(format!(
"q^k exceeds enum guard {MAX_ENUM}; distance not exhaustively verifiable — refusing to claim"
));
}
}
let qk = qk.unwrap();
let mut dmin = n + 1;
let mut msg = vec![0u64; k];
for code in 1..qk {
let mut x = code;
for m in msg.iter_mut() {
*m = x % q;
x /= q;
}
let mut weight = 0usize;
for c in 0..n {
let mut s = 0u64;
for i in 0..k {
if msg[i] != 0 {
s = (s + msg[i] * g[i][c]) % q;
}
}
if s != 0 {
weight += 1;
}
}
if weight < dmin {
dmin = weight;
}
}
let ok = dmin >= claimed_d;
let rel = if ok { ">=" } else { "<" };
VerifyResult {
ok,
message: format!(
"[{n},{k},{dmin}]_{q} verified (min weight {dmin} {rel} claimed {claimed_d})"
),
value: Some(dmin as f64),
}
}
fn advance_with_replacement(idx: &mut [usize], m: usize) -> bool {
let h = idx.len();
let mut i = h;
loop {
if i == 0 {
return false;
}
i -= 1;
if idx[i] != m - 1 {
let nv = idx[i] + 1;
for slot in idx.iter_mut().take(h).skip(i) {
*slot = nv;
}
return true;
}
}
}
fn each_combination(n: usize, t: usize, f: &mut impl FnMut(&[usize])) {
if t > n {
return;
}
let mut idx: Vec<usize> = (0..t).collect();
loop {
f(&idx);
let mut i = t;
loop {
if i == 0 {
return;
}
i -= 1;
if idx[i] != i + n - t {
idx[i] += 1;
for j in (i + 1)..t {
idx[j] = idx[j - 1] + 1;
}
break;
}
}
}
}
fn is_prime(q: u64) -> bool {
if q < 2 {
return false;
}
let mut p = 2u64;
while p * p <= q {
if q.is_multiple_of(p) {
return false;
}
p += 1;
}
true
}
#[allow(clippy::needless_range_loop)]
fn gf_rank(rows: &[Vec<u64>], q: u64) -> usize {
let mut m: Vec<Vec<u64>> = rows.to_vec();
if m.is_empty() {
return 0;
}
let ncols = m[0].len();
let mut rank = 0usize;
for col in 0..ncols {
let piv = (rank..m.len()).find(|&r| !m[r][col].is_multiple_of(q));
let Some(piv) = piv else { continue };
m.swap(rank, piv);
let inv = mod_inv(m[rank][col] % q, q);
for c in 0..ncols {
m[rank][c] = (m[rank][c] * inv) % q;
}
for r in 0..m.len() {
if r != rank && !m[r][col].is_multiple_of(q) {
let f = m[r][col] % q;
for c in 0..ncols {
m[r][c] = (m[r][c] + q - (f * m[rank][c]) % q) % q;
}
}
}
rank += 1;
if rank == m.len() {
break;
}
}
rank
}
fn mod_inv(a: u64, q: u64) -> u64 {
mod_pow(a, q - 2, q)
}
fn mod_pow(mut base: u64, mut exp: u64, modulus: u64) -> u64 {
let mut result = 1u64;
base %= modulus;
while exp > 0 {
if exp & 1 == 1 {
result = (result * base) % modulus;
}
exp >>= 1;
base = (base * base) % modulus;
}
result
}
#[cfg(test)]
mod tests {
use super::*;
fn small_sidon() -> Vec<Vec<i64>> {
vec![vec![0, 0, 0], vec![1, 0, 0], vec![0, 1, 0], vec![0, 0, 1]]
}
#[test]
fn faithful_parses_real_a309370_assertion() {
let text = "OEIS A309370 a(20) >= 1989: a Sidon set of 1989 distinct binary \
vectors in {0,1}^20 under componentwise integer addition, with all \
pairwise sums distinct. Frozen-verified by vela-verify (sidon kind).";
let p = parse_claim(text).expect("should parse the canonical A309370 form");
assert_eq!(p.kind, "sidon");
assert_eq!(p.ambient_n, Some(20));
assert_eq!(p.bound, 1989);
assert!(!p.exact);
}
#[test]
fn faithful_happy_path() {
let text = "a(3) >= 4: a Sidon set of 4 vectors in {0,1}^3.";
let w = Witness::Sidon {
n: 3,
points: small_sidon(),
claimed_size: Some(4),
};
let f = claim_witness_faithful(text, &w);
assert!(f.faithful, "{:?}", f.reasons);
}
#[test]
fn faithful_rejects_inflated_lower_bound() {
let text = "a(3) >= 5: a Sidon set of 5 vectors in {0,1}^3.";
let w = Witness::Sidon {
n: 3,
points: small_sidon(), claimed_size: None,
};
assert!(verify_witness(&w).ok, "the witness itself is valid");
let f = claim_witness_faithful(text, &w);
assert!(!f.faithful);
assert!(f.reasons.iter().any(|r| r.contains("does not establish")));
}
#[test]
fn faithful_rejects_dimension_mismatch() {
let text = "a(8) >= 4: a Sidon set of 4 vectors in {0,1}^8.";
let w = Witness::Sidon {
n: 3,
points: small_sidon(),
claimed_size: None,
};
let f = claim_witness_faithful(text, &w);
assert!(!f.faithful);
assert!(f.reasons.iter().any(|r| r.contains("dimension")));
}
#[test]
fn faithful_rejects_kind_mismatch() {
let text = "an optimal Golomb ruler of order 4 with >= 4 marks.";
let w = Witness::Sidon {
n: 3,
points: small_sidon(),
claimed_size: None,
};
let f = claim_witness_faithful(text, &w);
assert!(!f.faithful);
assert!(f.reasons.iter().any(|r| r.contains("kind")));
}
#[test]
fn faithful_rejects_invalid_witness() {
let text = "a(3) >= 4: a Sidon set of 4 vectors in {0,1}^3.";
let w = Witness::Sidon {
n: 3,
points: vec![vec![0, 0, 0], vec![1, 0, 0], vec![1, 0, 0], vec![0, 1, 0]],
claimed_size: None,
};
let f = claim_witness_faithful(text, &w);
assert!(!f.faithful);
assert!(f.reasons.iter().any(|r| r.contains("does not verify")));
}
#[test]
fn faithful_refuses_unparseable_asymptotic_claim() {
let text = "Singer's perfect-difference-set construction yields Sidon sets in \
{1,...,N} of size sqrt(N) + O(N^{1/4}).";
let w = Witness::Sidon {
n: 3,
points: small_sidon(),
claimed_size: None,
};
let f = claim_witness_faithful(text, &w);
assert!(!f.faithful);
assert!(f.parsed.is_none());
}
#[test]
fn faithful_refuses_ambiguous_bound() {
let text = "a Sidon set in {0,1}^3 with >= 4 and exactly 5 elements.";
assert!(parse_claim(text).is_none());
}
#[test]
fn faithful_routes_equality_optimality_to_review() {
let w = Witness::Sidon {
n: 3,
points: small_sidon(), claimed_size: None,
};
let f = claim_witness_faithful("a Sidon set in {0,1}^3 with exactly 4 elements.", &w);
assert!(
!f.faithful,
"equality/optimality is not witness-establishable"
);
assert!(f.reasons.iter().any(|r| r.contains("equality/optimality")));
let f2 = claim_witness_faithful("Sidon a(3) = 4 in {0,1}^3 (new record).", &w);
assert!(!f2.faithful, "a `= N` headline also routes to review");
}
#[test]
fn faithful_binds_a_of_n_order_to_witness() {
let w = Witness::Sidon {
n: 3,
points: small_sidon(),
claimed_size: None,
}; assert!(verify_witness(&w).ok, "the witness itself is valid");
let f = claim_witness_faithful("Sidon record a(20): at least 4 points.", &w);
assert!(
!f.faithful,
"an a(20) claim cannot ride an n=3 witness: {:?}",
f.reasons
);
let f2 = claim_witness_faithful("A Sidon set, at least 4 points, beats the record.", &w);
assert!(
!f2.faithful,
"a dimensioned claim with no ambient routes to review: {:?}",
f2.reasons
);
}
#[test]
fn faithful_rejects_dual_bound_headline() {
let w = Witness::Sidon {
n: 3,
points: small_sidon(),
claimed_size: None,
};
let f = claim_witness_faithful(
"Sidon in {0,1}^3: a(3) = 2500 (beats prior 1989). The witness has at least 4 points.",
&w,
);
assert!(
!f.faithful,
"a `= headline` beside an `at least` clause is ambiguous: {:?}",
f.reasons
);
assert!(
f.parsed.is_none(),
"the dual lower+equality marker fails parse"
);
}
#[test]
fn faithful_gf2_binds_dimension() {
let good = Witness::Gf2Sidon {
elements: vec![1, 2, 4],
claimed_size: None,
};
assert!(verify_witness(&good).ok);
let f = claim_witness_faithful("OEIS A394031 a(3) >= 3: a Sidon set in GF(2)^3.", &good);
assert!(f.faithful, "genuine GF(2)^3 claim: {:?}", f.reasons);
let wide = Witness::Gf2Sidon {
elements: vec![1, 2, 4, 8, 16],
claimed_size: None,
};
assert!(
verify_witness(&wide).ok,
"the wider witness is itself valid"
);
let f2 = claim_witness_faithful("OEIS A394031 a(4) >= 5: a Sidon set in GF(2)^4.", &wide);
assert!(
!f2.faithful,
"an element outside GF(2)^4 must fail: {:?}",
f2.reasons
);
let f3 = claim_witness_faithful("A GF(2) Sidon set, at least 5 elements.", &wide);
assert!(!f3.faithful, "{:?}", f3.reasons);
}
#[test]
fn faithful_binds_bh_order_and_constant_weight_params() {
let bh = Witness::Bh {
n: 3,
h: 2,
points: small_sidon(),
claimed_size: None,
};
assert!(verify_witness(&bh).ok, "the B_2 witness is itself valid");
let attack = claim_witness_faithful("a B_3 set in {0,1}^3: a(3) >= 4.", &bh);
assert!(
!attack.faithful,
"B_3 claim cannot ride a B_2 witness: {:?}",
attack.reasons
);
assert!(attack.reasons.iter().any(|r| r.contains("does not match")));
let ok = claim_witness_faithful("a B_2 set in {0,1}^3: a(3) >= 4.", &bh);
assert!(ok.faithful, "matched B_2 claim: {:?}", ok.reasons);
let bare = claim_witness_faithful("a bh set in {0,1}^3: a(3) >= 4.", &bh);
assert!(
!bare.faithful,
"unstated h routes to review: {:?}",
bare.reasons
);
let cw = Witness::ConstantWeight {
n: 4,
d: 2,
w: 1,
words: vec![vec![1, 0, 0, 0], vec![0, 1, 0, 0]],
claimed_size: None,
};
assert!(
verify_witness(&cw).ok,
"the A(4,2,1) witness is itself valid"
);
let attack2 = claim_witness_faithful("constant weight code A(4,10,8) >= 2.", &cw);
assert!(
!attack2.faithful,
"A(4,10,8) claim cannot ride an A(4,2,1) witness: {:?}",
attack2.reasons
);
assert!(attack2.reasons.iter().any(|r| r.contains("does not match")));
let ok2 = claim_witness_faithful("constant weight code A(4,2,1) >= 2.", &cw);
assert!(ok2.faithful, "matched A(4,2,1) claim: {:?}", ok2.reasons);
let bare2 = claim_witness_faithful("a constant weight code, a(4) >= 2.", &cw);
assert!(
!bare2.faithful,
"unstated (d,w) routes to review: {:?}",
bare2.reasons
);
}
#[test]
fn canonical_claim_is_witness_derived() {
let s = Witness::Sidon {
n: 3,
points: small_sidon(),
claimed_size: None,
};
let c = canonical_claim(&s).expect("sidon has a canonical claim");
assert!(c.contains("a(3) >= 4"), "{c}");
let g = Witness::Gf2Sidon {
elements: vec![1, 2, 4],
claimed_size: None,
};
let cg = canonical_claim(&g).expect("gf2 has a canonical claim");
assert!(cg.contains("a(3) >= 3"), "{cg}");
assert!(
canonical_claim(&Witness::Golomb {
marks: vec![0, 1, 3]
})
.is_none()
);
}
#[test]
fn faithful_golomb_routes_to_review() {
let w = Witness::Golomb {
marks: vec![0, 1, 3],
};
assert!(verify_witness(&w).ok);
let f = claim_witness_faithful("Golomb ruler a(3) >= 3.", &w);
assert!(
!f.faithful,
"golomb is not floor-admissible: {:?}",
f.reasons
);
}
#[test]
fn diff_triangle_accepts_valid_and_reports_scope() {
let w = Witness::DiffTriangle {
rows: vec![vec![0, 1, 3], vec![0, 4, 9]],
claimed_scope: Some(9),
};
let r = verify_witness(&w);
assert!(r.ok, "{}", r.message);
assert!(r.message.contains("scope 9"));
}
#[test]
fn diff_triangle_rejects_global_difference_collision() {
let w = Witness::DiffTriangle {
rows: vec![vec![0, 1, 3], vec![0, 2, 5]],
claimed_scope: None,
};
let r = verify_witness(&w);
assert!(!r.ok);
assert!(r.message.contains("repeats"));
}
#[test]
fn diff_triangle_rejects_non_increasing_and_nonzero_start() {
assert!(!verify_diff_triangle(&[vec![0, 3, 1]], None).ok);
assert!(!verify_diff_triangle(&[vec![1, 2, 4]], None).ok);
}
#[test]
fn diff_triangle_rejects_inflated_scope_claim() {
let w = Witness::DiffTriangle {
rows: vec![vec![0, 1, 3], vec![0, 4, 9]],
claimed_scope: Some(100),
};
assert!(!verify_witness(&w).ok);
}
#[test]
fn gf2_sidon_accepts_distinct_xors_and_rejects_collision() {
let ok = Witness::Gf2Sidon {
elements: vec![0, 1, 2],
claimed_size: Some(3),
};
assert!(verify_witness(&ok).ok);
let bad = Witness::Gf2Sidon {
elements: vec![0, 1, 2, 3],
claimed_size: None,
};
assert!(!verify_witness(&bad).ok);
let dup = Witness::Gf2Sidon {
elements: vec![5, 5],
claimed_size: None,
};
assert!(!verify_witness(&dup).ok);
}
#[test]
fn union_free_accepts_and_rejects_union_member() {
let ok = Witness::UnionFree {
n: 3,
sets: vec![vec![1, 2], vec![1, 3], vec![2, 3]],
claimed_size: Some(3),
};
assert!(verify_witness(&ok).ok);
let bad = Witness::UnionFree {
n: 2,
sets: vec![vec![1], vec![2], vec![1, 2]],
claimed_size: None,
};
assert!(!verify_witness(&bad).ok);
}
#[test]
fn rook_directions_counts_classes_and_checks_claim() {
let ok = Witness::RookDirections {
n: 2,
perm: vec![1, 2],
claimed_directions: Some(1),
};
assert!(verify_witness(&ok).ok);
let bad = Witness::RookDirections {
n: 2,
perm: vec![1, 2],
claimed_directions: Some(2),
};
assert!(!verify_witness(&bad).ok);
let attack = Witness::RookDirections {
n: 2,
perm: vec![1, 1],
claimed_directions: None,
};
assert!(!verify_witness(&attack).ok);
}
#[test]
fn unsat_cert_accepts_rup_proofs_and_rejects_corruption() {
let w = Witness::UnsatCert {
cnf: vec![vec![1], vec![-1]],
proof: vec![LratStep {
id: 3,
literals: vec![],
hints: vec![1, 2],
rat_hints: vec![],
}],
};
assert!(verify_witness(&w).ok);
let w2 = Witness::UnsatCert {
cnf: vec![vec![1], vec![2], vec![-1, -2]],
proof: vec![LratStep {
id: 4,
literals: vec![],
hints: vec![1, 2, 3],
rat_hints: vec![],
}],
};
assert!(verify_witness(&w2).ok);
let bad = Witness::UnsatCert {
cnf: vec![vec![1], vec![2], vec![-1, -2]],
proof: vec![LratStep {
id: 4,
literals: vec![],
hints: vec![1, 2],
rat_hints: vec![],
}],
};
assert!(!verify_witness(&bad).ok);
let sat = Witness::UnsatCert {
cnf: vec![vec![1, 2]],
proof: vec![LratStep {
id: 2,
literals: vec![],
hints: vec![1],
rat_hints: vec![],
}],
};
assert!(!verify_witness(&sat).ok);
}
#[test]
fn crt_partial_cover_accepts_real_rows_and_rejects_corruption() {
let m = "8168305011630835886634520238999";
let rows = vec![
CrtCoverRow {
p: 5,
ord2: 4,
ord3: 4,
h: 4,
t_p: 1,
m_mod_p: 4,
line: [1, 3, 0, 4],
},
CrtCoverRow {
p: 7,
ord2: 3,
ord3: 6,
h: 6,
t_p: 1,
m_mod_p: 6,
line: [2, 1, 0, 6],
},
];
assert!(verify_crt_partial_cover(m, &rows).ok);
let mut bad = rows.clone();
bad[0].t_p = 2;
assert!(!verify_crt_partial_cover(m, &bad).ok);
let mut bad = rows.clone();
bad[1].line = [2, 1, 1, 6];
assert!(!verify_crt_partial_cover(m, &bad).ok);
assert!(!verify_crt_partial_cover("9", &rows).ok);
}
#[test]
fn kummer_no_carry_accepts_erdos684_table_and_rejects_corruption() {
let entries = vec![
KummerEntry { k: 3, m: 36 },
KummerEntry { k: 7, m: 88200 },
KummerEntry { k: 12, m: 64033200 },
];
assert!(verify_kummer_no_carry(&entries).ok);
let bad = vec![KummerEntry { k: 3, m: 72 }];
assert!(!verify_kummer_no_carry(&bad).ok);
assert!(!verify_kummer_no_carry(&[KummerEntry { k: 25, m: 1 }]).ok);
}
#[test]
fn min_binom_gcd_accepts_erdos700_cases_and_rejects_corruption() {
let cases = vec![
MinGcdCase { n: 30, f: 6 },
MinGcdCase { n: 77, f: 7 },
MinGcdCase { n: 49, f: 7 },
];
assert!(verify_min_binom_gcd(&cases).ok);
assert!(!verify_min_binom_gcd(&[MinGcdCase { n: 30, f: 5 }]).ok);
}
#[test]
fn binom_deficiency_accepts_els93_row_and_rejects_corruption() {
let good = DeficiencyEntry {
k: 8,
n: "44".to_string(),
delta: 2,
slots: Some(vec![4, 6]),
};
assert!(verify_binom_deficiency(&[good.clone()]).ok);
let count_only = DeficiencyEntry {
slots: None,
..good.clone()
};
assert!(verify_binom_deficiency(&[count_only]).ok);
let bad = DeficiencyEntry {
delta: 1,
slots: None,
..good.clone()
};
assert!(!verify_binom_deficiency(&[bad]).ok);
let bad = DeficiencyEntry {
slots: Some(vec![4, 7]),
..good
};
assert!(!verify_binom_deficiency(&[bad]).ok);
let big = DeficiencyEntry {
k: 129,
n: "3180883073384828665489".to_string(),
delta: 1,
slots: Some(vec![65]),
};
assert!(verify_binom_deficiency(&[big]).ok);
}
#[test]
fn binom_exception_enum_matches_els_for_small_k_and_rejects_corruption() {
let els8: Vec<(u64, u64)> = vec![(7, 3), (13, 4), (14, 4), (23, 5), (62, 6), (44, 8)];
assert!(verify_binom_exception_enum(8, &els8).ok);
assert!(!verify_binom_exception_enum(8, &els8[1..]).ok);
let mut padded = els8.clone();
padded.push((100, 5));
assert!(!verify_binom_exception_enum(8, &padded).ok);
}
#[test]
fn interval_product_accepts_erdos1056_example_and_rejects_corruption() {
assert!(verify_interval_product(11, &[2, 4, 7]).ok);
assert!(!verify_interval_product(12, &[2, 4, 7]).ok);
assert!(!verify_interval_product(11, &[2, 4, 8]).ok);
assert!(!verify_interval_product(11, &[4, 4, 7]).ok);
}
#[test]
fn sidon_accepts_valid_and_rejects_corrupted() {
assert!(verify_sidon(&small_sidon(), 3).ok);
let mut bad = small_sidon();
bad.push(vec![1, 1, 0]);
assert!(!verify_sidon(&bad, 3).ok, "corrupted Sidon must fail");
}
#[test]
fn packed_binary_sidon_path_matches_coordinate_semantics() {
let good = small_sidon();
let result = verify_sidon(&good, 3);
assert!(result.ok, "{}", result.message);
assert!(result.message.contains("10 pairwise sums"));
let collision = vec![vec![0, 0, 0], vec![1, 0, 0], vec![0, 1, 0], vec![1, 1, 0]];
assert!(!verify_sidon(&collision, 3).ok);
}
#[test]
fn sidon_rejects_non_binary_and_dups() {
assert!(!verify_sidon(&[vec![0, 2, 0]], 3).ok);
assert!(!verify_sidon(&[vec![1, 0, 0], vec![1, 0, 0]], 3).ok);
}
#[test]
fn claimed_size_mismatch_fails() {
let w = Witness::Sidon {
n: 3,
points: small_sidon(),
claimed_size: Some(99),
};
let r = verify_witness(&w);
assert!(!r.ok, "claimed_size 99 != actual 4 must fail");
assert!(r.message.contains("claimed_size"));
}
#[test]
fn golomb_accepts_valid_and_rejects_corrupted() {
assert!(verify_golomb(&[0, 1, 4, 6]).ok);
assert!(!verify_golomb(&[0, 1, 2, 4]).ok);
}
#[test]
fn cap_accepts_valid_and_rejects_collinear() {
assert!(verify_cap(&[vec![0], vec![1]], 1).ok);
assert!(!verify_cap(&[vec![0], vec![1], vec![2]], 1).ok);
}
#[test]
fn bh_h2_matches_sidon() {
assert!(verify_bh(&small_sidon(), 3, 2).ok);
let mut bad = small_sidon();
bad.push(vec![1, 1, 0]);
assert!(!verify_bh(&bad, 3, 2).ok);
}
#[test]
fn covering_accepts_full_and_rejects_gap() {
let full = vec![vec![0, 1, 2], vec![0, 1, 3], vec![0, 2, 3], vec![1, 2, 3]];
assert!(verify_covering(&full, 4, 3, 2).ok);
let gap = vec![vec![0, 1, 2], vec![0, 1, 3]];
assert!(!verify_covering(&gap, 4, 3, 2).ok);
}
#[test]
fn constant_weight_checks_weight_and_distance() {
let ok = vec![vec![1, 1, 0, 0], vec![0, 0, 1, 1]];
assert!(verify_constant_weight(&ok, 4, 2, 2).ok);
assert!(!verify_constant_weight(&[vec![1, 1, 1, 0]], 4, 2, 2).ok);
}
#[test]
fn costas_accepts_valid_and_rejects_nonpermutation() {
assert!(verify_costas(&[0, 2, 3, 1]).ok);
assert!(!verify_costas(&[0, 0, 1, 2]).ok);
}
#[test]
fn linear_code_verifies_distance_and_refuses_nonprime() {
let g = vec![vec![1, 1, 1]];
let r = verify_linear_code(&g, 2, 3);
assert!(r.ok, "{}", r.message);
assert!(!verify_linear_code(&g, 2, 4).ok);
assert!(!verify_linear_code(&g, 4, 1).ok);
}
#[test]
fn witness_serde_round_trip() {
let w = Witness::Sidon {
n: 3,
points: small_sidon(),
claimed_size: Some(4),
};
let json = serde_json::to_string(&w).unwrap();
assert!(json.contains("\"kind\":\"sidon\""));
let back: Witness = serde_json::from_str(&json).unwrap();
assert_eq!(back, w);
assert!(verify_witness(&back).ok);
}
}
#[cfg(test)]
mod balanced_coloring_tests {
use super::*;
use std::collections::BTreeMap;
fn pentagon_k5() -> BTreeMap<String, u32> {
let pent = [(0, 1), (1, 2), (2, 3), (3, 4), (0, 4)];
let mut ec = BTreeMap::new();
for i in 0..5usize {
for j in (i + 1)..5 {
let c = if pent.contains(&(i, j)) { 1 } else { 2 };
ec.insert(format!("{i},{j}"), c);
}
}
ec
}
#[test]
fn pentagon_coloring_is_balanced() {
let r = verify_balanced_coloring(5, 2, &pentagon_k5());
assert!(r.ok, "{}", r.message);
}
#[test]
fn flipped_edge_breaks_balance() {
let mut ec = pentagon_k5();
ec.insert("0,1".to_string(), 2);
let r = verify_balanced_coloring(5, 2, &ec);
assert!(!r.ok);
}
#[test]
fn dominates_orders_by_n_at_same_r() {
let w5 = Witness::BalancedColoring {
n: 5,
r: 2,
edge_colors: pentagon_k5(),
};
let w4 = Witness::BalancedColoring {
n: 4,
r: 2,
edge_colors: BTreeMap::new(),
};
assert_eq!(dominates(&w5, &w4), Ok(true));
assert_eq!(dominates(&w4, &w5), Ok(false));
}
}
#[cfg(test)]
mod rat_tests {
use super::*;
fn rat_cert() -> (Vec<Vec<i64>>, Vec<LratStep>) {
let cnf = vec![vec![1, 2], vec![-1, 3], vec![2], vec![-2]];
let proof = vec![
LratStep {
id: 5,
literals: vec![-1, -2],
hints: vec![],
rat_hints: vec![],
},
LratStep {
id: 6,
literals: vec![],
hints: vec![3, 4],
rat_hints: vec![],
},
];
(cnf, proof)
}
#[test]
fn blocked_clause_step_verifies_as_rat() {
let (cnf, proof) = rat_cert();
let r = verify_unsat_cert(&cnf, &proof);
assert!(r.ok, "{}", r.message);
}
#[test]
fn rat_step_with_unhinted_resolvent_is_rejected() {
let (mut cnf, proof) = rat_cert();
cnf.push(vec![1, -3]);
let r = verify_unsat_cert(&cnf, &proof);
assert!(!r.ok);
assert!(
r.message.contains("neither RUP-implied nor RAT"),
"{}",
r.message
);
}
#[test]
fn rat_with_supplied_resolvent_hints_verifies() {
let (mut cnf, mut proof) = rat_cert();
cnf.push(vec![1, -3]); proof[0].id = 6;
proof[0].rat_hints = vec![(5, vec![4])];
proof[1].id = 7;
let r = verify_unsat_cert(&cnf, &proof);
assert!(r.ok, "{}", r.message);
}
#[test]
fn unit_fraction_decomp_checks_exactness_coverage_and_ordering() {
let c = |n, x, y, z| UnitFractionCase { n, x, y, z };
let good = vec![c(3, 1, 4, 12), c(4, 2, 3, 6), c(5, 2, 4, 20)];
assert!(verify_unit_fraction_decomp(5, &good).ok);
assert!(!verify_unit_fraction_decomp(5, &[c(3, 1, 4, 12), c(5, 2, 4, 20)]).ok);
assert!(!verify_unit_fraction_decomp(3, &[c(3, 1, 4, 13)]).ok);
assert!(!verify_unit_fraction_decomp(4, &[c(3, 1, 4, 12), c(4, 2, 6, 6)]).ok);
assert!(!verify_unit_fraction_decomp(3, &[c(3, 1, 4, 12), c(7, 2, 4, 28)]).ok);
}
#[test]
fn distinct_partial_sums_checks_validity_coverage_and_primality() {
let full = vec![vec![1u64], vec![2], vec![1, 2]];
assert!(verify_distinct_partial_sums(3, &full).ok);
assert!(!verify_distinct_partial_sums(3, &[vec![1u64], vec![1, 2]]).ok);
assert!(!verify_distinct_partial_sums(3, &[vec![1u64], vec![2], vec![1, 5]]).ok);
assert!(!verify_distinct_partial_sums(4, &[vec![1u64]]).ok);
}
#[test]
fn powerful_triples_none_confirms_no_triple_and_counts_pairs() {
let r = verify_powerful_triples_none(1000, None);
assert!(r.ok, "{}", r.message);
assert!(r.message.contains("pairs exist"));
assert!(!verify_powerful_triples_none(1000, Some(0)).ok);
assert!(verify_powerful_triples_none(10, None).ok);
}
#[test]
fn two_full_three_full_finds_the_complete_set() {
assert!(verify_two_full_three_full(100, &[]).ok);
assert!(!verify_two_full_three_full(100, &[8]).ok);
assert!(verify_two_full_three_full(10, &[]).ok);
}
fn brocard_witness(n: u64) -> u64 {
fn is_prime(n: u64) -> bool {
if n < 2 {
return false;
}
let mut d = 2;
while d * d <= n {
if n.is_multiple_of(d) {
return false;
}
d += 1;
}
true
}
fn modpow(mut b: u128, mut e: u128, m: u128) -> u128 {
let mut r = 1u128;
b %= m;
while e > 0 {
if e & 1 == 1 {
r = r * b % m;
}
e >>= 1;
b = b * b % m;
}
r
}
let mut p = n + 1;
loop {
if is_prime(p) {
let pm = p as u128;
let mut f = 1u128;
for k in 1..=n {
f = f * (k as u128) % pm;
}
let r = (f + 1) % pm;
if r != 0 && modpow(r, (pm - 1) / 2, pm) == pm - 1 {
return p;
}
}
p += 1;
}
}
#[test]
fn brocard_no_square_certifies_a_range_and_rejects_tampering() {
let (n_min, n_max) = (8u64, 40u64);
let cases: Vec<BrocardCase> = (n_min..=n_max)
.map(|n| BrocardCase {
n,
p: brocard_witness(n),
})
.collect();
let w = Witness::BrocardNoSquare {
n_min,
n_max,
cases: cases.clone(),
};
let r = verify_witness(&w);
assert!(r.ok, "should certify [{n_min},{n_max}]: {}", r.message);
let known = Witness::BrocardNoSquare {
n_min: 4,
n_max: 7,
cases: vec![
BrocardCase { n: 4, p: 0 },
BrocardCase { n: 5, p: 0 },
BrocardCase {
n: 6,
p: brocard_witness(6),
},
BrocardCase { n: 7, p: 0 },
],
};
assert!(
verify_witness(&known).ok,
"4,5,7 are the known squares; 6 is not"
);
let mut bad = cases.clone();
bad[0].p = bad[0].n * (bad[0].n + 1); assert!(
!verify_witness(&Witness::BrocardNoSquare {
n_min,
n_max,
cases: bad,
})
.ok,
"a non-prime witness must fail"
);
let short: Vec<BrocardCase> = cases[1..].to_vec();
assert!(
!verify_witness(&Witness::BrocardNoSquare {
n_min,
n_max,
cases: short,
})
.ok,
"incomplete coverage must fail"
);
assert!(
!verify_witness(&Witness::BrocardNoSquare {
n_min: 8,
n_max: 8,
cases: vec![BrocardCase { n: 8, p: 0 }],
})
.ok,
"n=8 with no witnessing prime must fail (8 is not a known square and p=0 invalid)"
);
}
#[test]
fn semiprime_egyptian_checks_decompositions_and_rejections() {
let good = Witness::SemiprimeEgyptian {
cases: vec![
SemiprimeEgyptianCase {
a: 1,
b: 6,
denominators: vec![6],
},
SemiprimeEgyptianCase {
a: 4,
b: 15,
denominators: vec![6, 10],
},
SemiprimeEgyptianCase {
a: 7,
b: 30,
denominators: vec![6, 15],
},
SemiprimeEgyptianCase {
a: 1,
b: 3,
denominators: vec![6, 10, 15],
},
],
};
let r = verify_witness(&good);
assert!(r.ok, "valid semiprime-Egyptian cases: {}", r.message);
assert!(
!verify_semiprime_egyptian(&[SemiprimeEgyptianCase {
a: 1,
b: 12,
denominators: vec![12],
}])
.ok,
"12 is not a squarefree semiprime"
);
assert!(
!verify_semiprime_egyptian(&[SemiprimeEgyptianCase {
a: 1,
b: 30,
denominators: vec![30],
}])
.ok,
"30 has three prime factors"
);
assert!(
!verify_semiprime_egyptian(&[SemiprimeEgyptianCase {
a: 1,
b: 5,
denominators: vec![6],
}])
.ok,
"1/6 != 1/5"
);
assert!(
!verify_semiprime_egyptian(&[SemiprimeEgyptianCase {
a: 4,
b: 15,
denominators: vec![10, 6],
}])
.ok,
"denominators must be strictly increasing"
);
assert!(
!verify_semiprime_egyptian(&[SemiprimeEgyptianCase {
a: 1,
b: 12,
denominators: vec![14, 21],
}])
.ok,
"b=12 is not squarefree"
);
}
}