1use std::collections::HashSet;
22
23use serde::{Deserialize, Serialize};
24
25pub const ENV_ID: &str = concat!("vela-verify@", env!("CARGO_PKG_VERSION"));
30
31#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
33pub struct VerifyResult {
34 pub ok: bool,
36 pub message: String,
38 #[serde(default, skip_serializing_if = "Option::is_none")]
41 pub value: Option<f64>,
42}
43
44impl VerifyResult {
45 pub fn ok(message: impl Into<String>) -> Self {
46 Self {
47 ok: true,
48 message: message.into(),
49 value: None,
50 }
51 }
52 pub fn fail(message: impl Into<String>) -> Self {
53 Self {
54 ok: false,
55 message: message.into(),
56 value: None,
57 }
58 }
59}
60
61#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
69#[serde(tag = "kind", rename_all = "snake_case")]
70pub enum Witness {
71 Sidon {
74 n: usize,
75 points: Vec<Vec<i64>>,
76 #[serde(default, skip_serializing_if = "Option::is_none")]
77 claimed_size: Option<usize>,
78 },
79 Golomb { marks: Vec<i64> },
82 Cap {
84 n: usize,
85 points: Vec<Vec<i64>>,
86 #[serde(default, skip_serializing_if = "Option::is_none")]
87 claimed_size: Option<usize>,
88 },
89 Bh {
92 n: usize,
93 h: usize,
94 points: Vec<Vec<i64>>,
95 #[serde(default, skip_serializing_if = "Option::is_none")]
96 claimed_size: Option<usize>,
97 },
98 Covering {
101 v: usize,
102 k: usize,
103 t: usize,
104 blocks: Vec<Vec<usize>>,
105 },
106 ConstantWeight {
109 n: usize,
110 d: usize,
111 w: usize,
112 words: Vec<Vec<i64>>,
113 #[serde(default, skip_serializing_if = "Option::is_none")]
114 claimed_size: Option<usize>,
115 },
116 Costas { perm: Vec<i64> },
119 Gf2Sidon {
123 elements: Vec<u64>,
124 #[serde(default, skip_serializing_if = "Option::is_none")]
125 claimed_size: Option<usize>,
126 },
127 UnionFree {
133 n: usize,
134 sets: Vec<Vec<u32>>,
135 #[serde(default, skip_serializing_if = "Option::is_none")]
136 claimed_size: Option<usize>,
137 },
138 RookDirections {
144 n: usize,
145 perm: Vec<i64>,
146 #[serde(default, skip_serializing_if = "Option::is_none")]
147 claimed_directions: Option<usize>,
148 },
149 LinearCode {
152 q: u64,
153 claimed_d: usize,
154 generator: Vec<Vec<i64>>,
155 },
156 IntervalProduct { p: u64, cuts: Vec<u64> },
160 BalancedColoring {
166 n: usize,
167 r: usize,
168 edge_colors: std::collections::BTreeMap<String, u32>,
169 },
170 CrtPartialCover { m: String, rows: Vec<CrtCoverRow> },
177 KummerNoCarry { entries: Vec<KummerEntry> },
182 MinBinomGcd { cases: Vec<MinGcdCase> },
187 BinomDeficiency { entries: Vec<DeficiencyEntry> },
194 BinomExceptionEnum {
201 k_max: u64,
202 exceptions: Vec<(u64, u64)>,
203 },
204 UnsatCert {
213 cnf: Vec<Vec<i64>>,
214 proof: Vec<LratStep>,
215 },
216 DiffTriangle {
224 rows: Vec<Vec<i64>>,
225 #[serde(default, skip_serializing_if = "Option::is_none")]
226 claimed_scope: Option<usize>,
227 },
228 UnitFractionDecomp {
237 n_max: u64,
238 cases: Vec<UnitFractionCase>,
239 },
240 DistinctPartialSums { p: u64, orderings: Vec<Vec<u64>> },
250 PowerfulTriplesNone {
259 n_max: u64,
260 #[serde(default, skip_serializing_if = "Option::is_none")]
261 pairs_claimed: Option<u64>,
262 },
263 TwoFullThreeFull { n_max: u64, examples: Vec<u64> },
271 BrocardNoSquare {
279 n_min: u64,
280 n_max: u64,
281 cases: Vec<BrocardCase>,
282 },
283 SemiprimeEgyptian { cases: Vec<SemiprimeEgyptianCase> },
291}
292
293#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
297pub struct LratStep {
298 pub id: u64,
299 pub literals: Vec<i64>,
300 pub hints: Vec<u64>,
301 #[serde(default, skip_serializing_if = "Vec::is_empty")]
307 pub rat_hints: Vec<(u64, Vec<u64>)>,
308}
309
310#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
312pub struct CrtCoverRow {
313 pub p: u64,
314 pub ord2: u64,
315 pub ord3: u64,
316 pub h: u64,
317 pub t_p: u64,
318 pub m_mod_p: u64,
319 pub line: [u64; 4],
321}
322
323#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
325pub struct KummerEntry {
326 pub k: u64,
327 pub m: u64,
328}
329
330#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
332pub struct MinGcdCase {
333 pub n: u64,
334 pub f: u64,
335}
336
337#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
340pub struct UnitFractionCase {
341 pub n: u64,
342 pub x: u64,
343 pub y: u64,
344 pub z: u64,
345}
346
347#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
355pub struct BrocardCase {
356 pub n: u64,
357 #[serde(default)]
358 pub p: u64,
359}
360
361#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
366pub struct SemiprimeEgyptianCase {
367 pub a: u64,
368 pub b: u64,
369 pub denominators: Vec<u64>,
370}
371
372#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
376pub struct DeficiencyEntry {
377 pub k: u64,
378 pub n: String,
379 pub delta: u64,
380 #[serde(default, skip_serializing_if = "Option::is_none")]
381 pub slots: Option<Vec<u64>>,
382}
383
384impl Witness {
385 pub fn kind(&self) -> &'static str {
387 match self {
388 Witness::Sidon { .. } => "sidon",
389 Witness::Golomb { .. } => "golomb",
390 Witness::Cap { .. } => "cap",
391 Witness::Bh { .. } => "bh",
392 Witness::Covering { .. } => "covering",
393 Witness::ConstantWeight { .. } => "constant_weight",
394 Witness::Costas { .. } => "costas",
395 Witness::Gf2Sidon { .. } => "gf2_sidon",
396 Witness::UnionFree { .. } => "union_free",
397 Witness::RookDirections { .. } => "rook_directions",
398 Witness::LinearCode { .. } => "linear_code",
399 Witness::IntervalProduct { .. } => "interval_product",
400 Witness::BalancedColoring { .. } => "balanced_coloring",
401 Witness::CrtPartialCover { .. } => "crt_partial_cover",
402 Witness::KummerNoCarry { .. } => "kummer_no_carry",
403 Witness::MinBinomGcd { .. } => "min_binom_gcd",
404 Witness::BinomDeficiency { .. } => "binom_deficiency",
405 Witness::BinomExceptionEnum { .. } => "binom_exception_enum",
406 Witness::UnsatCert { .. } => "unsat_cert",
407 Witness::DiffTriangle { .. } => "diff_triangle",
408 Witness::UnitFractionDecomp { .. } => "unit_fraction_decomp",
409 Witness::DistinctPartialSums { .. } => "distinct_partial_sums",
410 Witness::PowerfulTriplesNone { .. } => "powerful_triples_none",
411 Witness::TwoFullThreeFull { .. } => "two_full_three_full",
412 Witness::BrocardNoSquare { .. } => "brocard_no_square",
413 Witness::SemiprimeEgyptian { .. } => "semiprime_egyptian",
414 }
415 }
416}
417
418pub fn verify_diff_triangle(rows: &[Vec<i64>], claimed_scope: Option<usize>) -> VerifyResult {
424 if rows.is_empty() {
425 return VerifyResult::fail("empty difference triangle set");
426 }
427 let mut diffs: HashSet<i64> = HashSet::new();
428 let mut diff_count = 0usize;
429 let mut scope: i64 = 0;
430 for (r, row) in rows.iter().enumerate() {
431 if row.len() < 2 {
432 return VerifyResult::fail(format!("row {r} has fewer than 2 marks"));
433 }
434 if row[0] != 0 {
435 return VerifyResult::fail(format!("row {r} does not start at 0"));
436 }
437 for w in row.windows(2) {
439 if w[1] <= w[0] {
440 return VerifyResult::fail(format!("row {r} is not strictly increasing"));
441 }
442 }
443 scope = scope.max(*row.last().unwrap());
444 for i in 0..row.len() {
446 for j in (i + 1)..row.len() {
447 let d = row[j] - row[i];
448 if !diffs.insert(d) {
449 return VerifyResult::fail(format!(
450 "difference {d} repeats (row {r}) — not a difference triangle set"
451 ));
452 }
453 diff_count += 1;
454 }
455 }
456 }
457 let scope_usize = scope as usize;
458 if let Some(c) = claimed_scope
459 && c != scope_usize
460 {
461 return VerifyResult::fail(format!(
462 "verifier passed but scope {scope_usize} != claimed_scope {c}"
463 ));
464 }
465 VerifyResult::ok(format!(
466 "difference triangle set: {} rows, scope {scope_usize}, all {diff_count} within-row differences globally distinct",
467 rows.len()
468 ))
469}
470
471pub fn dominates(new: &Witness, prior: &Witness) -> Result<bool, String> {
479 use Witness::*;
480 match (new, prior) {
481 (
482 Sidon {
483 n: n1, points: p1, ..
484 },
485 Sidon {
486 n: n2, points: p2, ..
487 },
488 ) => {
489 if n1 != n2 {
490 return Err(format!("different n ({n1} vs {n2}); not comparable"));
491 }
492 Ok(p1.len() > p2.len())
493 }
494 (Golomb { marks: m1, .. }, Golomb { marks: m2, .. }) => Ok(m1.len() > m2.len()),
495 (BalancedColoring { n: n1, r: r1, .. }, BalancedColoring { n: n2, r: r2, .. }) => {
496 if r1 != r2 {
497 return Err(format!("different r ({r1} vs {r2}); not comparable"));
498 }
499 Ok(n1 > n2)
500 }
501 (IntervalProduct { p: p1, cuts: c1 }, IntervalProduct { p: p2, cuts: c2 }) => {
502 if p1 == p2 {
503 Ok(c1.len() > c2.len())
504 } else {
505 Ok(c1.len() > c2.len())
507 }
508 }
509 _ => Err(format!(
510 "no dominance order defined between {} and {}",
511 new.kind(),
512 prior.kind()
513 )),
514 }
515}
516
517pub fn verify_witness(witness: &Witness) -> VerifyResult {
518 match witness {
519 Witness::Sidon {
520 n,
521 points,
522 claimed_size,
523 } => with_size(verify_sidon(points, *n), points.len(), *claimed_size),
524 Witness::Golomb { marks } => verify_golomb(marks),
525 Witness::Cap {
526 n,
527 points,
528 claimed_size,
529 } => with_size(verify_cap(points, *n), points.len(), *claimed_size),
530 Witness::Bh {
531 n,
532 h,
533 points,
534 claimed_size,
535 } => with_size(verify_bh(points, *n, *h), points.len(), *claimed_size),
536 Witness::Covering { v, k, t, blocks } => verify_covering(blocks, *v, *k, *t),
537 Witness::IntervalProduct { p, cuts } => verify_interval_product(*p, cuts),
538 Witness::BalancedColoring { n, r, edge_colors } => {
539 verify_balanced_coloring(*n, *r, edge_colors)
540 }
541 Witness::CrtPartialCover { m, rows } => verify_crt_partial_cover(m, rows),
542 Witness::KummerNoCarry { entries } => verify_kummer_no_carry(entries),
543 Witness::MinBinomGcd { cases } => verify_min_binom_gcd(cases),
544 Witness::BinomDeficiency { entries } => verify_binom_deficiency(entries),
545 Witness::BinomExceptionEnum { k_max, exceptions } => {
546 verify_binom_exception_enum(*k_max, exceptions)
547 }
548 Witness::UnsatCert { cnf, proof } => verify_unsat_cert(cnf, proof),
549 Witness::ConstantWeight {
550 n,
551 d,
552 w,
553 words,
554 claimed_size,
555 } => with_size(
556 verify_constant_weight(words, *n, *d, *w),
557 words.len(),
558 *claimed_size,
559 ),
560 Witness::Costas { perm } => verify_costas(perm),
561 Witness::Gf2Sidon {
562 elements,
563 claimed_size,
564 } => with_size(verify_gf2_sidon(elements), elements.len(), *claimed_size),
565 Witness::UnionFree {
566 n,
567 sets,
568 claimed_size,
569 } => with_size(verify_union_free(*n, sets), sets.len(), *claimed_size),
570 Witness::RookDirections {
571 n,
572 perm,
573 claimed_directions,
574 } => verify_rook_directions(*n, perm, *claimed_directions),
575 Witness::LinearCode {
576 q,
577 claimed_d,
578 generator,
579 } => verify_linear_code(generator, *q, *claimed_d),
580 Witness::DiffTriangle {
581 rows,
582 claimed_scope,
583 } => verify_diff_triangle(rows, *claimed_scope),
584 Witness::UnitFractionDecomp { n_max, cases } => verify_unit_fraction_decomp(*n_max, cases),
585 Witness::DistinctPartialSums { p, orderings } => {
586 verify_distinct_partial_sums(*p, orderings)
587 }
588 Witness::PowerfulTriplesNone {
589 n_max,
590 pairs_claimed,
591 } => verify_powerful_triples_none(*n_max, *pairs_claimed),
592 Witness::TwoFullThreeFull { n_max, examples } => {
593 verify_two_full_three_full(*n_max, examples)
594 }
595 Witness::BrocardNoSquare {
596 n_min,
597 n_max,
598 cases,
599 } => verify_brocard_no_square(*n_min, *n_max, cases),
600 Witness::SemiprimeEgyptian { cases } => verify_semiprime_egyptian(cases),
601 }
602}
603
604pub fn verify_two_full_three_full(n_max: u64, examples: &[u64]) -> VerifyResult {
612 if n_max < 1 {
613 return VerifyResult::fail("n_max must be >= 1");
614 }
615 if n_max > 200_000_000 {
616 return VerifyResult::fail("n_max too large for the in-gate sieve (cap 2e8)");
617 }
618 let n = (n_max + 1) as usize; let mut spf = vec![0u32; n + 1];
620 for i in 2..=n {
621 if spf[i] == 0 {
622 let mut j = i;
623 while j <= n {
624 if spf[j] == 0 {
625 spf[j] = i as u32;
626 }
627 j += i;
628 }
629 }
630 }
631 let min_exp = |mut m: usize| -> u64 {
633 if m <= 1 {
634 return u64::MAX;
635 }
636 let mut lo = u64::MAX;
637 while m > 1 {
638 let p = spf[m] as usize;
639 let mut e = 0;
640 while m.is_multiple_of(p) {
641 m /= p;
642 e += 1;
643 }
644 lo = lo.min(e);
645 }
646 lo
647 };
648 let mut found: Vec<u64> = Vec::new();
649 for m in 1..=(n_max as usize) {
650 if min_exp(m) >= 2 && min_exp(m + 1) >= 3 {
651 found.push(m as u64);
652 }
653 }
654 let mut claimed = examples.to_vec();
655 claimed.sort_unstable();
656 if claimed != found {
657 return VerifyResult::fail(format!(
658 "claimed examples {claimed:?} != the {} actually found in [1, {n_max}]: {found:?}",
659 found.len()
660 ));
661 }
662 if found.is_empty() {
663 VerifyResult::ok(format!(
664 "Erdős #366 finite confirmation: NO 2-full n with n+1 3-full in [1, {n_max}]. \
665 The question over all integers is the open problem."
666 ))
667 } else {
668 VerifyResult::ok(format!(
669 "Erdős #366: {} genuine witness(es) in [1, {n_max}] — 2-full n with n+1 3-full: {found:?}. \
670 Exhibits existence (the set is complete over the range).",
671 found.len()
672 ))
673 }
674}
675
676pub fn verify_powerful_triples_none(n_max: u64, pairs_claimed: Option<u64>) -> VerifyResult {
682 if n_max < 3 {
683 return VerifyResult::fail("n_max must be >= 3");
684 }
685 if n_max > 200_000_000 {
686 return VerifyResult::fail("n_max too large for the in-gate sieve (cap 2e8)");
688 }
689 let n = n_max as usize;
690 let mut spf = vec![0u32; n + 1];
692 for i in 2..=n {
693 if spf[i] == 0 {
694 let mut j = i;
695 while j <= n {
696 if spf[j] == 0 {
697 spf[j] = i as u32;
698 }
699 j += i;
700 }
701 }
702 }
703 let is_powerful = |mut m: usize| -> bool {
705 if m == 1 {
706 return true;
707 }
708 while m > 1 {
709 let p = spf[m] as usize;
710 let mut e = 0;
711 while m.is_multiple_of(p) {
712 m /= p;
713 e += 1;
714 }
715 if e < 2 {
716 return false;
717 }
718 }
719 true
720 };
721 let mut pairs = 0u64;
722 let mut prev = is_powerful(1);
723 let mut prev2 = false;
724 for m in 2..=n {
725 let cur = is_powerful(m);
726 if cur && prev {
727 pairs += 1;
728 }
729 if cur && prev && prev2 {
730 return VerifyResult::fail(format!(
731 "found three consecutive powerful integers ending at {m} (#364 would be FALSIFIED)"
732 ));
733 }
734 prev2 = prev;
735 prev = cur;
736 }
737 if let Some(claimed) = pairs_claimed
738 && claimed != pairs
739 {
740 return VerifyResult::fail(format!(
741 "pairs_claimed {claimed} != {pairs} consecutive powerful pairs actually found"
742 ));
743 }
744 VerifyResult::ok(format!(
745 "Erdős #364 verified for [1, {n_max}]: no three consecutive powerful integers \
746 ({pairs} consecutive powerful pairs exist, e.g. 8,9). Finite confirmation; the \
747 question over all integers is the open problem."
748 ))
749}
750
751pub fn verify_distinct_partial_sums(p: u64, orderings: &[Vec<u64>]) -> VerifyResult {
758 let is_prime = |n: u64| -> bool {
759 if n < 2 {
760 return false;
761 }
762 let mut d = 2;
763 while d * d <= n {
764 if n.is_multiple_of(d) {
765 return false;
766 }
767 d += 1;
768 }
769 true
770 };
771 if !is_prime(p) {
772 return VerifyResult::fail(format!("p = {p} is not prime"));
773 }
774 let mut covered: HashSet<Vec<u64>> = HashSet::new();
777 for ord in orderings {
778 if ord.is_empty() {
779 return VerifyResult::fail("empty ordering (A must be nonempty)");
780 }
781 let set: HashSet<&u64> = ord.iter().collect();
783 if set.len() != ord.len() {
784 return VerifyResult::fail("ordering has a repeated element");
785 }
786 for &a in ord {
787 if a == 0 || a >= p {
788 return VerifyResult::fail(format!("element {a} not in F_{p}\\{{0}}"));
789 }
790 }
791 let mut seen: HashSet<u64> = HashSet::new();
793 let mut acc = 0u64;
794 for &a in ord {
795 acc = (acc + a) % p;
796 if !seen.insert(acc) {
797 let mut key: Vec<u64> = ord.clone();
798 key.sort_unstable();
799 return VerifyResult::fail(format!(
800 "subset {key:?}: ordering {ord:?} has a repeated partial sum mod {p}"
801 ));
802 }
803 }
804 let mut key: Vec<u64> = ord.clone();
805 key.sort_unstable();
806 if !covered.insert(key.clone()) {
807 return VerifyResult::fail(format!("subset {key:?} covered more than once"));
808 }
809 }
810 let expected = (1u64 << (p - 1)) - 1; if covered.len() as u64 != expected {
812 return VerifyResult::fail(format!(
813 "incomplete coverage: {} of {expected} nonempty subsets of F_{p}\\{{0}}",
814 covered.len()
815 ));
816 }
817 VerifyResult::ok(format!(
818 "Erdős #475 (distinct partial sums) verified for ALL nonempty A ⊆ F_{p}\\{{0}}: \
819 {expected} subsets, each orderable with distinct partial sums mod {p}. \
820 Finite confirmation; the question over all primes is the open problem."
821 ))
822}
823
824pub fn verify_unit_fraction_decomp(n_max: u64, cases: &[UnitFractionCase]) -> VerifyResult {
831 if n_max < 3 {
832 return VerifyResult::fail("n_max must be >= 3 (the conjecture is stated for n > 2)");
833 }
834 let mut seen: HashSet<u64> = HashSet::new();
836 for c in cases {
837 if c.n < 3 || c.n > n_max {
838 return VerifyResult::fail(format!("case n={} is outside [3, {n_max}]", c.n));
839 }
840 if !seen.insert(c.n) {
841 return VerifyResult::fail(format!("duplicate case for n={}", c.n));
842 }
843 if !(1 <= c.x && c.x < c.y && c.y < c.z) {
845 return VerifyResult::fail(format!(
846 "n={}: triple ({},{},{}) is not 1 <= x < y < z",
847 c.n, c.x, c.y, c.z
848 ));
849 }
850 let (n, x, y, z) = (c.n as u128, c.x as u128, c.y as u128, c.z as u128);
852 let lhs = 4u128 * x * y * z;
853 let rhs = n * (y * z + x * z + x * y);
854 if lhs != rhs {
855 return VerifyResult::fail(format!(
856 "n={}: 4/{} != 1/{}+1/{}+1/{} (exact check failed)",
857 c.n, c.n, c.x, c.y, c.z
858 ));
859 }
860 }
861 let expected = (n_max - 3 + 1) as usize;
862 if seen.len() != expected {
863 return VerifyResult::fail(format!(
864 "incomplete: covered {} of {expected} values in [3, {n_max}]",
865 seen.len()
866 ));
867 }
868 VerifyResult::ok(format!(
869 "Erdős–Straus (#242, distinct variant) verified for all 3 <= n <= {n_max}: \
870 {expected} exact decompositions 4/n = 1/x+1/y+1/z with x < y < z. \
871 Finite confirmation; the uniform proof over all n is the open problem."
872 ))
873}
874
875pub fn verify_brocard_no_square(n_min: u64, n_max: u64, cases: &[BrocardCase]) -> VerifyResult {
885 if n_min < 1 || n_max < n_min {
886 return VerifyResult::fail("require 1 <= n_min <= n_max");
887 }
888 if n_max > 5_000_000 {
889 return VerifyResult::fail("n_max too large for the in-gate certificate (cap 5e6)");
890 }
891 let is_prime = |n: u64| -> bool {
892 if n < 2 {
893 return false;
894 }
895 if n.is_multiple_of(2) {
896 return n == 2;
897 }
898 let mut d = 3u64;
899 while d * d <= n {
900 if n.is_multiple_of(d) {
901 return false;
902 }
903 d += 2;
904 }
905 true
906 };
907 let mod_pow = |mut base: u128, mut exp: u128, modulus: u128| -> u128 {
909 if modulus == 1 {
910 return 0;
911 }
912 let mut result = 1u128;
913 base %= modulus;
914 while exp > 0 {
915 if exp & 1 == 1 {
916 result = result * base % modulus;
917 }
918 exp >>= 1;
919 base = base * base % modulus;
920 }
921 result
922 };
923 let known: [u64; 3] = [4, 5, 7];
925 let mut seen: HashSet<u64> = HashSet::new();
926 for c in cases {
927 if c.n < n_min || c.n > n_max {
928 return VerifyResult::fail(format!("case n={} outside [{n_min}, {n_max}]", c.n));
929 }
930 if !seen.insert(c.n) {
931 return VerifyResult::fail(format!("duplicate case for n={}", c.n));
932 }
933 if known.contains(&c.n) {
934 let mut fact: u128 = 1;
936 for k in 1..=c.n as u128 {
937 fact *= k;
938 }
939 let val = fact + 1;
940 let root = (val as f64).sqrt() as u128;
941 let mut is_sq = false;
942 for m in root.saturating_sub(2)..=root + 2 {
943 if m * m == val {
944 is_sq = true;
945 break;
946 }
947 }
948 if !is_sq {
949 return VerifyResult::fail(format!(
950 "n={}: {}!+1 = {val} is not a perfect square (expected a known solution)",
951 c.n, c.n
952 ));
953 }
954 } else {
955 let p = c.p;
957 if p <= c.n {
958 return VerifyResult::fail(format!(
959 "n={}: witnessing prime p={p} must exceed n",
960 c.n
961 ));
962 }
963 if !is_prime(p) {
964 return VerifyResult::fail(format!("n={}: p={p} is not prime", c.n));
965 }
966 let pm = p as u128;
967 let mut fact = 1u128;
968 for k in 1..=c.n {
969 fact = fact * (k as u128) % pm;
970 }
971 let r = (fact + 1) % pm;
972 if r == 0 {
973 return VerifyResult::fail(format!(
974 "n={}: n!+1 ≡ 0 (mod {p}); that does not prove a non-square",
975 c.n
976 ));
977 }
978 let legendre = mod_pow(r, (pm - 1) / 2, pm);
980 if legendre != pm - 1 {
981 return VerifyResult::fail(format!(
982 "n={}: r={r} is a quadratic residue mod {p} \
983 (r^((p-1)/2) mod p = {legendre}, need {}); n!+1 not shown non-square",
984 c.n,
985 pm - 1
986 ));
987 }
988 }
989 }
990 let expected = (n_max - n_min + 1) as usize;
991 if seen.len() != expected {
992 return VerifyResult::fail(format!(
993 "incomplete: covered {} of {expected} values in [{n_min}, {n_max}]",
994 seen.len()
995 ));
996 }
997 let exceptions: Vec<u64> = known
998 .iter()
999 .copied()
1000 .filter(|&n| n >= n_min && n <= n_max)
1001 .collect();
1002 VerifyResult::ok(format!(
1003 "Erdős #398 (Brocard) verified for all {n_min} <= n <= {n_max}: n!+1 is a perfect \
1004 square exactly for n in {exceptions:?}, and a non-square (quadratic-non-residue \
1005 certificate mod a witnessing prime) for every other n. Finite confirmation; the \
1006 conjecture over all n is the open problem."
1007 ))
1008}
1009
1010pub fn verify_semiprime_egyptian(cases: &[SemiprimeEgyptianCase]) -> VerifyResult {
1018 if cases.is_empty() {
1019 return VerifyResult::fail("no cases supplied");
1020 }
1021 let gcd = |mut a: u64, mut b: u64| -> u64 {
1022 while b != 0 {
1023 let t = a % b;
1024 a = b;
1025 b = t;
1026 }
1027 a
1028 };
1029 let gcd128 = |mut a: u128, mut b: u128| -> u128 {
1030 while b != 0 {
1031 let t = a % b;
1032 a = b;
1033 b = t;
1034 }
1035 a
1036 };
1037 let is_squarefree_semiprime = |n: u64| -> bool {
1040 if n < 6 {
1041 return false;
1042 }
1043 let mut m = n;
1044 let mut factors = 0u32;
1045 let mut d = 2u64;
1046 while d * d <= m {
1047 if m.is_multiple_of(d) {
1048 let mut e = 0u32;
1049 while m.is_multiple_of(d) {
1050 m /= d;
1051 e += 1;
1052 }
1053 if e != 1 {
1054 return false; }
1056 factors += 1;
1057 }
1058 d += 1;
1059 }
1060 if m > 1 {
1061 factors += 1;
1062 }
1063 factors == 2
1064 };
1065 let is_squarefree = |mut n: u64| -> bool {
1066 let mut d = 2u64;
1067 while d * d <= n {
1068 if n.is_multiple_of(d) {
1069 n /= d;
1070 if n.is_multiple_of(d) {
1071 return false;
1072 }
1073 } else {
1074 d += 1;
1075 }
1076 }
1077 true
1078 };
1079 let mut seen: HashSet<(u64, u64)> = HashSet::new();
1080 for c in cases {
1081 if c.a == 0 || c.b == 0 {
1082 return VerifyResult::fail("a and b must be positive");
1083 }
1084 let g = gcd(c.a, c.b);
1085 let (ar, br) = (c.a / g, c.b / g);
1086 if !is_squarefree(br) {
1087 return VerifyResult::fail(format!(
1088 "{}/{}: reduced denominator {br} is not squarefree",
1089 c.a, c.b
1090 ));
1091 }
1092 if !seen.insert((ar, br)) {
1093 return VerifyResult::fail(format!("duplicate rational {ar}/{br}"));
1094 }
1095 let d = &c.denominators;
1096 if d.is_empty() {
1097 return VerifyResult::fail(format!("{ar}/{br}: empty denominator list"));
1098 }
1099 for w in d.windows(2) {
1100 if w[0] >= w[1] {
1101 return VerifyResult::fail(format!(
1102 "{ar}/{br}: denominators must be strictly increasing"
1103 ));
1104 }
1105 }
1106 for &ni in d {
1107 if !is_squarefree_semiprime(ni) {
1108 return VerifyResult::fail(format!(
1109 "{ar}/{br}: denominator {ni} is not a product of two distinct primes"
1110 ));
1111 }
1112 }
1113 let mut sn: u128 = 0;
1115 let mut sd: u128 = 1;
1116 for &ni in d {
1117 let ni = ni as u128;
1118 let nn = sn.checked_mul(ni).and_then(|v| v.checked_add(sd));
1119 let nd = sd.checked_mul(ni);
1120 match (nn, nd) {
1121 (Some(nn), Some(nd)) => {
1122 let g = gcd128(nn, nd).max(1);
1123 sn = nn / g;
1124 sd = nd / g;
1125 }
1126 _ => {
1127 return VerifyResult::fail(format!(
1128 "{ar}/{br}: denominator product overflow (expansion too long/large)"
1129 ));
1130 }
1131 }
1132 }
1133 let lhs = sn.checked_mul(br as u128);
1135 let rhs = (ar as u128).checked_mul(sd);
1136 match (lhs, rhs) {
1137 (Some(l), Some(r)) if l == r => {}
1138 (Some(_), Some(_)) => {
1139 return VerifyResult::fail(format!(
1140 "{ar}/{br}: sum of 1/n_i = {sn}/{sd} != {ar}/{br}"
1141 ));
1142 }
1143 _ => {
1144 return VerifyResult::fail(format!("{ar}/{br}: overflow comparing the exact sum"));
1145 }
1146 }
1147 }
1148 VerifyResult::ok(format!(
1149 "Erdős #306 verified: {} reduced a/b (b squarefree) each exhibited as an Egyptian \
1150 expansion into distinct squarefree-semiprime unit fractions. Per-instance finite \
1151 confirmation; the question over all positive rationals is the open problem.",
1152 cases.len()
1153 ))
1154}
1155
1156#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
1161pub struct ParsedClaim {
1162 pub kind: String,
1164 pub ambient_n: Option<usize>,
1168 pub bound: usize,
1170 pub exact: bool,
1174 #[serde(default, skip_serializing_if = "Option::is_none")]
1177 pub h: Option<usize>,
1178 #[serde(default, skip_serializing_if = "Option::is_none")]
1182 pub d: Option<usize>,
1183 #[serde(default, skip_serializing_if = "Option::is_none")]
1184 pub w: Option<usize>,
1185}
1186
1187#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
1199pub struct Faithfulness {
1200 pub faithful: bool,
1201 pub reasons: Vec<String>,
1202 #[serde(default, skip_serializing_if = "Option::is_none")]
1203 pub parsed: Option<ParsedClaim>,
1204}
1205
1206fn leading_usize(s: &str) -> Option<usize> {
1208 let s = s.trim_start();
1209 let digits: String = s.chars().take_while(|c| c.is_ascii_digit()).collect();
1210 if digits.is_empty() {
1211 None
1212 } else {
1213 digits.parse().ok()
1214 }
1215}
1216
1217fn usize_after_any(hay: &str, needles: &[&str]) -> Option<usize> {
1220 let mut best: Option<(usize, usize)> = None; for needle in needles {
1222 if let Some(idx) = hay.find(needle)
1223 && let Some(v) = leading_usize(&hay[idx + needle.len()..])
1224 && best.map(|(_, p)| idx < p).unwrap_or(true)
1225 {
1226 best = Some((v, idx));
1227 }
1228 }
1229 best.map(|(v, _)| v)
1230}
1231
1232fn order_in_a_paren(text: &str) -> Option<usize> {
1236 text.find("a(").and_then(|i| leading_usize(&text[i + 2..]))
1237}
1238
1239fn equality_bound(text: &str) -> Option<usize> {
1245 if let Some(v) = usize_after_any(text, &["exactly "]) {
1246 return Some(v);
1247 }
1248 let mut from = 0;
1249 while let Some(rel) = text[from..].find('=') {
1250 let idx = from + rel;
1251 let prev = text[..idx].chars().last();
1252 let compound = matches!(
1253 prev,
1254 Some('>') | Some('<') | Some('!') | Some('=') | Some('\u{2265}') | Some('\u{2264}')
1255 );
1256 if !compound && let Some(v) = leading_usize(&text[idx + 1..]) {
1257 return Some(v);
1258 }
1259 from = idx + 1;
1260 }
1261 None
1262}
1263
1264fn bh_order(text: &str) -> Option<usize> {
1268 let subscript = text.find("b_").and_then(|i| leading_usize(&text[i + 2..]));
1269 let fold = text.find("-fold").and_then(|i| {
1270 let pre: String = text[..i]
1271 .chars()
1272 .rev()
1273 .take_while(|c| c.is_ascii_digit())
1274 .collect();
1275 pre.chars().rev().collect::<String>().parse().ok()
1276 });
1277 match (subscript, fold) {
1278 (Some(a), Some(b)) if a != b => None,
1279 (Some(a), _) => Some(a),
1280 (None, Some(b)) => Some(b),
1281 (None, None) => None,
1282 }
1283}
1284
1285fn cw_params(text: &str) -> Option<(usize, usize, usize)> {
1289 let i = text.find("a(")?;
1290 let rest = &text[i + 2..];
1291 let close = rest.find(')')?;
1292 let parts: Vec<&str> = rest[..close].split(',').collect();
1293 if parts.len() != 3 {
1294 return None;
1295 }
1296 Some((
1297 parts[0].trim().parse().ok()?,
1298 parts[1].trim().parse().ok()?,
1299 parts[2].trim().parse().ok()?,
1300 ))
1301}
1302
1303pub fn parse_claim(assertion_text: &str) -> Option<ParsedClaim> {
1309 let text = assertion_text.to_lowercase();
1310
1311 let kind = if text.contains("gf(2)") && text.contains("sidon") {
1313 "gf2_sidon"
1314 } else if text.contains("sidon") {
1315 "sidon"
1316 } else if text.contains("golomb") {
1317 "golomb"
1318 } else if text.contains("cap set") || text.contains("cap-set") {
1319 "cap"
1320 } else if text.contains("b_h") || text.contains("bh set") || bh_order(&text).is_some() {
1321 "bh"
1322 } else if text.contains("constant weight") || text.contains("constant-weight") {
1323 "constant_weight"
1324 } else if text.contains("union-free") || text.contains("union free") {
1325 "union_free"
1326 } else {
1327 return None;
1328 };
1329
1330 let order = order_in_a_paren(&text);
1336 let literal = ["{0,1}^", "gf(2)^", "f_3^"].iter().find_map(|m| {
1337 text.find(m)
1338 .and_then(|i| leading_usize(&text[i + m.len()..]))
1339 });
1340 let ambient_n = match (order, literal) {
1341 (Some(a), Some(b)) if a != b => return None,
1342 (Some(a), _) => Some(a),
1343 (None, Some(b)) => Some(b),
1344 (None, None) => None,
1345 };
1346
1347 let lower = usize_after_any(&text, &[">=", "\u{2265}", "at least "]);
1353 let equality = equality_bound(&text);
1354 let (bound, is_exact) = match (lower, equality) {
1355 (Some(l), None) => (l, false),
1356 (None, Some(e)) => (e, true),
1357 _ => return None,
1359 };
1360
1361 let h = bh_order(&text);
1363 let (d, w) = match cw_params(&text) {
1364 Some((_, d, w)) => (Some(d), Some(w)),
1365 None => (None, None),
1366 };
1367
1368 Some(ParsedClaim {
1369 kind: kind.to_string(),
1370 ambient_n,
1371 bound,
1372 exact: is_exact,
1373 h,
1374 d,
1375 w,
1376 })
1377}
1378
1379pub fn claim_witness_faithful(assertion_text: &str, witness: &Witness) -> Faithfulness {
1384 verify_witness_with_claim(assertion_text, witness).1
1385}
1386
1387pub fn verify_witness_with_claim(
1394 assertion_text: &str,
1395 witness: &Witness,
1396) -> (VerifyResult, Faithfulness) {
1397 let verification = verify_witness(witness);
1398 let faithfulness =
1399 claim_witness_faithful_from_verification(assertion_text, witness, &verification);
1400 (verification, faithfulness)
1401}
1402
1403fn claim_witness_faithful_from_verification(
1404 assertion_text: &str,
1405 witness: &Witness,
1406 verification: &VerifyResult,
1407) -> Faithfulness {
1408 let mut reasons = Vec::new();
1409
1410 let Some(parsed) = parse_claim(assertion_text) else {
1411 reasons.push(
1412 "assertion does not parse to a recognized exact-lane claim (kind keyword + a single \
1413 unambiguous >=/exactly bound); routes to review"
1414 .to_string(),
1415 );
1416 return Faithfulness {
1417 faithful: false,
1418 reasons,
1419 parsed: None,
1420 };
1421 };
1422
1423 if !verification.ok {
1425 reasons.push(format!("witness does not verify: {}", verification.message));
1426 return Faithfulness {
1427 faithful: false,
1428 reasons,
1429 parsed: Some(parsed),
1430 };
1431 }
1432
1433 if parsed.kind != witness.kind() {
1435 reasons.push(format!(
1436 "claim kind '{}' does not match witness kind '{}'",
1437 parsed.kind,
1438 witness.kind()
1439 ));
1440 return Faithfulness {
1441 faithful: false,
1442 reasons,
1443 parsed: Some(parsed),
1444 };
1445 }
1446
1447 if parsed.exact {
1452 reasons.push(
1453 "equality/optimality claim (= / exactly) is not establishable by a construction \
1454 witness (which proves only a lower bound); routes to review"
1455 .to_string(),
1456 );
1457 return Faithfulness {
1458 faithful: false,
1459 reasons,
1460 parsed: Some(parsed),
1461 };
1462 }
1463
1464 let dim_n_witness = |n: usize| -> Option<String> {
1470 match parsed.ambient_n {
1471 None => Some(
1472 "dimensioned claim states no ambient dimension (a(N) / {0,1}^N / gf(2)^N); \
1473 routes to review"
1474 .to_string(),
1475 ),
1476 Some(c) if c != n => Some(format!(
1477 "claim ambient dimension n={c} does not match witness n={n}"
1478 )),
1479 Some(_) => None,
1480 }
1481 };
1482
1483 let size: usize = match witness {
1493 Witness::Sidon { n, points, .. } | Witness::Cap { n, points, .. } => {
1494 if let Some(r) = dim_n_witness(*n) {
1495 reasons.push(r);
1496 return Faithfulness {
1497 faithful: false,
1498 reasons,
1499 parsed: Some(parsed),
1500 };
1501 }
1502 points.len()
1503 }
1504 Witness::UnionFree { n, sets, .. } => {
1505 if let Some(r) = dim_n_witness(*n) {
1506 reasons.push(r);
1507 return Faithfulness {
1508 faithful: false,
1509 reasons,
1510 parsed: Some(parsed),
1511 };
1512 }
1513 sets.len()
1514 }
1515 Witness::Gf2Sidon { elements, .. } => {
1516 let Some(claim_n) = parsed.ambient_n else {
1520 reasons.push(
1521 "GF(2)-Sidon claim states no dimension N (a(N) / gf(2)^N); routes to review"
1522 .to_string(),
1523 );
1524 return Faithfulness {
1525 faithful: false,
1526 reasons,
1527 parsed: Some(parsed),
1528 };
1529 };
1530 if claim_n >= 64 || elements.iter().any(|e| (*e >> claim_n) != 0) {
1531 reasons.push(format!(
1532 "witness has an element outside GF(2)^{claim_n}; it does not establish a(N) \
1533 at that dimension"
1534 ));
1535 return Faithfulness {
1536 faithful: false,
1537 reasons,
1538 parsed: Some(parsed),
1539 };
1540 }
1541 elements.len()
1542 }
1543 Witness::Bh { n, h, points, .. } => {
1544 if let Some(r) = dim_n_witness(*n) {
1548 reasons.push(r);
1549 return Faithfulness {
1550 faithful: false,
1551 reasons,
1552 parsed: Some(parsed),
1553 };
1554 }
1555 match parsed.h {
1556 Some(ch) if ch == *h => {}
1557 Some(ch) => {
1558 reasons.push(format!(
1559 "claim B_{ch} does not match witness B_{h} (the order h binds the record)"
1560 ));
1561 return Faithfulness {
1562 faithful: false,
1563 reasons,
1564 parsed: Some(parsed),
1565 };
1566 }
1567 None => {
1568 reasons.push(
1569 "B_h claim does not state the order h (B_<h> / <h>-fold); routes to review"
1570 .to_string(),
1571 );
1572 return Faithfulness {
1573 faithful: false,
1574 reasons,
1575 parsed: Some(parsed),
1576 };
1577 }
1578 }
1579 points.len()
1580 }
1581 Witness::ConstantWeight { n, d, w, words, .. } => {
1582 if let Some(r) = dim_n_witness(*n) {
1587 reasons.push(r);
1588 return Faithfulness {
1589 faithful: false,
1590 reasons,
1591 parsed: Some(parsed),
1592 };
1593 }
1594 match (parsed.d, parsed.w) {
1595 (Some(cd), Some(cw)) if cd == *d && cw == *w => {}
1596 (Some(cd), Some(cw)) => {
1597 reasons.push(format!(
1598 "claim A(n,{cd},{cw}) does not match witness A(n,{d},{w}) (d,w bind the record)"
1599 ));
1600 return Faithfulness {
1601 faithful: false,
1602 reasons,
1603 parsed: Some(parsed),
1604 };
1605 }
1606 _ => {
1607 reasons.push(
1608 "constant-weight claim does not state (d,w) as A(n,d,w); routes to review"
1609 .to_string(),
1610 );
1611 return Faithfulness {
1612 faithful: false,
1613 reasons,
1614 parsed: Some(parsed),
1615 };
1616 }
1617 }
1618 words.len()
1619 }
1620 Witness::Golomb { .. } => {
1621 reasons.push(
1625 "golomb claims are not floor-admissible (no sound witness->bound binding \
1626 defined); routes to review"
1627 .to_string(),
1628 );
1629 return Faithfulness {
1630 faithful: false,
1631 reasons,
1632 parsed: Some(parsed),
1633 };
1634 }
1635 _ => {
1637 reasons.push(format!(
1638 "witness kind '{}' is not an exact-lane size/order claim",
1639 witness.kind()
1640 ));
1641 return Faithfulness {
1642 faithful: false,
1643 reasons,
1644 parsed: Some(parsed),
1645 };
1646 }
1647 };
1648
1649 if size < parsed.bound {
1650 reasons.push(format!(
1651 "witness size/order {size} does not establish the claimed >= {}",
1652 parsed.bound
1653 ));
1654 return Faithfulness {
1655 faithful: false,
1656 reasons,
1657 parsed: Some(parsed),
1658 };
1659 }
1660
1661 Faithfulness {
1662 faithful: true,
1663 reasons,
1664 parsed: Some(parsed),
1665 }
1666}
1667
1668pub fn canonical_claim(witness: &Witness) -> Option<String> {
1676 match witness {
1677 Witness::Sidon { n, points, .. } => Some(format!(
1678 "Sidon set: a({n}) >= {} (a Sidon set of {} points in {{0,1}}^{n})",
1679 points.len(),
1680 points.len()
1681 )),
1682 Witness::Cap { n, points, .. } => Some(format!(
1683 "cap set: a({n}) >= {} (a cap set of {} points in F_3^{n})",
1684 points.len(),
1685 points.len()
1686 )),
1687 Witness::Gf2Sidon { elements, .. } => {
1688 let n = elements
1691 .iter()
1692 .map(|e| (64 - e.leading_zeros()) as usize)
1693 .max()
1694 .unwrap_or(0);
1695 Some(format!(
1696 "GF(2)-Sidon set: a({n}) >= {} (a Sidon set of {} elements in GF(2)^{n})",
1697 elements.len(),
1698 elements.len()
1699 ))
1700 }
1701 Witness::UnionFree { n, sets, .. } => Some(format!(
1702 "union-free family: a({n}) >= {} (a union-free family of {} subsets of {{1..{n}}})",
1703 sets.len(),
1704 sets.len()
1705 )),
1706 Witness::Bh { n, h, points, .. } => Some(format!(
1707 "B_{h} set: a({n}) >= {} (a B_{h} set of {} points in {{0,1}}^{n})",
1708 points.len(),
1709 points.len()
1710 )),
1711 Witness::ConstantWeight { n, d, w, words, .. } => Some(format!(
1712 "constant-weight code: A({n},{d},{w}) >= {} ({} codewords of length {n}, weight {w}, min distance {d})",
1713 words.len(),
1714 words.len()
1715 )),
1716 _ => None,
1718 }
1719}
1720
1721fn with_size(mut r: VerifyResult, actual: usize, claimed: Option<usize>) -> VerifyResult {
1724 if r.ok
1725 && let Some(c) = claimed
1726 {
1727 if actual != c {
1728 return VerifyResult::fail(format!(
1729 "verifier passed but construction size {actual} != claimed_size {c}"
1730 ));
1731 }
1732 r.message = format!("{} (size {actual} = claimed)", r.message);
1733 }
1734 r
1735}
1736
1737fn binary_points_ok(points: &[Vec<i64>], n: usize) -> Option<VerifyResult> {
1740 let set: HashSet<&Vec<i64>> = points.iter().collect();
1741 if set.len() != points.len() {
1742 return Some(VerifyResult::fail("duplicate points"));
1743 }
1744 if !points
1745 .iter()
1746 .all(|p| p.len() == n && p.iter().all(|&x| x == 0 || x == 1))
1747 {
1748 return Some(VerifyResult::fail(format!("points not binary length-{n}")));
1749 }
1750 None
1751}
1752
1753pub fn verify_sidon(points: &[Vec<i64>], n: usize) -> VerifyResult {
1756 if let Some(bad) = binary_points_ok(points, n) {
1757 return bad;
1758 }
1759 let m = points.len();
1760 if n <= 32 {
1761 let Some(pair_count) = m
1762 .checked_add(1)
1763 .and_then(|next| m.checked_mul(next))
1764 .map(|value| value / 2)
1765 else {
1766 return VerifyResult::fail("pairwise-sum count overflows this platform");
1767 };
1768 let expanded = points
1769 .iter()
1770 .map(|point| {
1771 point
1772 .iter()
1773 .enumerate()
1774 .fold(0_u64, |packed, (index, value)| {
1775 packed | ((*value as u64) << (2 * index))
1776 })
1777 })
1778 .collect::<Vec<_>>();
1779 let mut sums = Vec::new();
1780 if sums.try_reserve_exact(pair_count).is_err() {
1781 return VerifyResult::fail("insufficient memory for pairwise-sum check");
1782 }
1783 for i in 0..m {
1784 for j in i..m {
1785 sums.push(expanded[i] + expanded[j]);
1788 }
1789 }
1790 sums.sort_unstable();
1791 if sums.windows(2).any(|pair| pair[0] == pair[1]) {
1792 return VerifyResult::fail("pairwise-sum collision (not Sidon)");
1793 }
1794 return VerifyResult::ok(format!(
1795 "Sidon verified: {m} points, {pair_count} pairwise sums all distinct"
1796 ));
1797 }
1798 let mut sums: HashSet<Vec<i64>> = HashSet::new();
1799 let mut count = 0usize;
1800 for i in 0..m {
1801 for j in i..m {
1802 let s: Vec<i64> = (0..n).map(|k| points[i][k] + points[j][k]).collect();
1803 if !sums.insert(s) {
1804 return VerifyResult::fail("pairwise-sum collision (not Sidon)");
1805 }
1806 count += 1;
1807 }
1808 }
1809 VerifyResult::ok(format!(
1810 "Sidon verified: {m} points, {count} pairwise sums all distinct"
1811 ))
1812}
1813
1814#[must_use]
1819pub fn verify_gf2_sidon(elements: &[u64]) -> VerifyResult {
1820 let m = elements.len();
1821 let distinct: HashSet<u64> = elements.iter().copied().collect();
1822 if distinct.len() != m {
1823 return VerifyResult::fail("duplicate element (not a set)");
1824 }
1825 let mut xors: HashSet<u64> = HashSet::new();
1826 let mut count = 0usize;
1827 for i in 0..m {
1828 for j in (i + 1)..m {
1829 let x = elements[i] ^ elements[j];
1830 if x == 0 {
1831 return VerifyResult::fail("zero XOR (equal elements)");
1832 }
1833 if !xors.insert(x) {
1834 return VerifyResult::fail("pairwise-XOR collision (not a GF(2) Sidon set)");
1835 }
1836 count += 1;
1837 }
1838 }
1839 VerifyResult::ok(format!(
1840 "GF(2)-Sidon verified: {m} elements, {count} pairwise XORs all distinct"
1841 ))
1842}
1843
1844fn gcd_pos(a: i64, b: i64) -> i64 {
1847 let (mut a, mut b) = (a.abs(), b.abs());
1848 while b != 0 {
1849 let t = b;
1850 b = a % b;
1851 a = t;
1852 }
1853 if a == 0 { 1 } else { a }
1854}
1855
1856#[must_use]
1862pub fn verify_union_free(n: usize, sets: &[Vec<u32>]) -> VerifyResult {
1863 if n == 0 || n > 63 {
1864 return VerifyResult::fail("n out of range (1..=63)");
1865 }
1866 let mut masks: Vec<u64> = Vec::with_capacity(sets.len());
1867 for s in sets {
1868 if s.is_empty() {
1869 return VerifyResult::fail("empty set (members must be nonempty)");
1870 }
1871 let mut m = 0u64;
1872 for &e in s {
1873 if e < 1 || (e as usize) > n {
1874 return VerifyResult::fail(format!("element {e} out of {{1..{n}}}"));
1875 }
1876 m |= 1u64 << (e - 1);
1877 }
1878 masks.push(m);
1879 }
1880 let distinct: HashSet<u64> = masks.iter().copied().collect();
1881 if distinct.len() != masks.len() {
1882 return VerifyResult::fail("duplicate set (members must be distinct)");
1883 }
1884 for (i, &c) in masks.iter().enumerate() {
1885 let mut u = 0u64;
1886 for (j, &s) in masks.iter().enumerate() {
1887 if i != j && (s & c) == s {
1888 u |= s;
1889 }
1890 }
1891 if u == c {
1892 return VerifyResult::fail(
1893 "a member is the union of a sub-collection of the others (not union-free)",
1894 );
1895 }
1896 }
1897 VerifyResult::ok(format!(
1898 "union-free verified: {} sets over {{1..{n}}}, no member is a union of others",
1899 masks.len()
1900 ))
1901}
1902
1903#[must_use]
1909pub fn verify_rook_directions(n: usize, perm: &[i64], claimed: Option<usize>) -> VerifyResult {
1910 if perm.len() != n {
1911 return VerifyResult::fail("perm length != n");
1912 }
1913 let mut seen = vec![false; n + 1];
1914 for &c in perm {
1915 if c < 1 || (c as usize) > n {
1916 return VerifyResult::fail("column out of 1..=n");
1917 }
1918 if seen[c as usize] {
1919 return VerifyResult::fail("repeated column (attacking rooks)");
1920 }
1921 seen[c as usize] = true;
1922 }
1923 let mut classes: HashSet<(i64, i64)> = HashSet::new();
1924 for i in 0..n {
1925 for j in (i + 1)..n {
1926 let drow = (j as i64) - (i as i64);
1927 let dcol = perm[j] - perm[i];
1928 let g = gcd_pos(dcol, drow);
1929 let (a, b) = (dcol.abs() / g, drow.abs() / g);
1930 classes.insert(if a <= b { (a, b) } else { (b, a) });
1931 }
1932 }
1933 let count = classes.len();
1934 if let Some(cl) = claimed
1935 && count != cl
1936 {
1937 return VerifyResult::fail(format!("direction count {count} != claimed {cl}"));
1938 }
1939 VerifyResult::ok(format!(
1940 "rook-directions verified: {n} non-attacking rooks realize {count} distinct direction classes"
1941 ))
1942}
1943
1944pub fn verify_balanced_coloring(
1954 n: usize,
1955 r: usize,
1956 edge_colors: &std::collections::BTreeMap<String, u32>,
1957) -> VerifyResult {
1958 if r < 2 || n < r + 1 {
1959 return VerifyResult::fail(format!("need r >= 2 and n >= r+1 (got n={n}, r={r})"));
1960 }
1961 let mut color = vec![vec![0u32; n]; n];
1963 for (key, &c) in edge_colors {
1964 let Some((a, b)) = key.split_once(',') else {
1965 return VerifyResult::fail(format!("bad edge key '{key}' (want \"i,j\")"));
1966 };
1967 let (Ok(i), Ok(j)) = (a.trim().parse::<usize>(), b.trim().parse::<usize>()) else {
1968 return VerifyResult::fail(format!("bad edge key '{key}'"));
1969 };
1970 if i >= n || j >= n || i >= j {
1971 return VerifyResult::fail(format!("edge '{key}' out of range or not i<j for n={n}"));
1972 }
1973 if c == 0 || c as usize > r {
1974 return VerifyResult::fail(format!("edge '{key}' color {c} outside 1..={r}"));
1975 }
1976 color[i][j] = c;
1977 }
1978 for (i, row) in color.iter().enumerate() {
1979 for (j, &c) in row.iter().enumerate().skip(i + 1) {
1980 if c == 0 {
1981 return VerifyResult::fail(format!("edge {i},{j} is uncolored"));
1982 }
1983 }
1984 }
1985 let k = r + 1;
1988 let mut idx: Vec<usize> = (0..k).collect();
1989 let mut checked = 0u64;
1990 loop {
1991 let mut seen = vec![false; r + 1];
1992 for x in 0..k {
1993 for y in (x + 1)..k {
1994 seen[color[idx[x]][idx[y]] as usize] = true;
1995 }
1996 }
1997 if let Some(missing) = (1..=r).find(|&c| !seen[c]) {
1998 return VerifyResult::fail(format!("subset {:?} sees no edge of color {missing}", idx));
1999 }
2000 checked += 1;
2001 let mut pos = k;
2003 while pos > 0 {
2004 pos -= 1;
2005 if idx[pos] != pos + n - k {
2006 idx[pos] += 1;
2007 for q in (pos + 1)..k {
2008 idx[q] = idx[q - 1] + 1;
2009 }
2010 break;
2011 }
2012 if pos == 0 {
2013 return VerifyResult::ok(format!(
2014 "balanced {r}-coloring of K_{n} verified: {checked} {k}-subsets each see all {r} colors"
2015 ));
2016 }
2017 }
2018 }
2019}
2020
2021pub fn verify_interval_product(p: u64, cuts: &[u64]) -> VerifyResult {
2022 if !is_prime(p) {
2023 return VerifyResult::fail(format!("modulus p={p} must be prime"));
2024 }
2025 if cuts.len() < 2 {
2026 return VerifyResult::fail("need at least two cuts (one interval)");
2027 }
2028 for w in cuts.windows(2) {
2029 if w[0] >= w[1] {
2030 return VerifyResult::fail("cuts must be strictly increasing");
2031 }
2032 }
2033 for w in cuts.windows(2) {
2034 let mut prod: u64 = 1;
2035 for m in (w[0] + 1)..=w[1] {
2036 prod = ((prod as u128 * (m % p) as u128) % p as u128) as u64;
2037 }
2038 if prod != 1 {
2039 return VerifyResult::fail(format!(
2040 "interval ({}, {}] has product {prod} mod {p} != 1",
2041 w[0], w[1]
2042 ));
2043 }
2044 }
2045 VerifyResult::ok(format!(
2046 "Erdos #1056 certificate: prime p={p}, {} consecutive interval(s) each with product 1 mod p",
2047 cuts.len() - 1
2048 ))
2049}
2050
2051fn carries_base_p(mut a: u128, mut b: u128, p: u128) -> u64 {
2056 let mut carry: u128 = 0;
2057 let mut count: u64 = 0;
2058 while a > 0 || b > 0 || carry > 0 {
2059 let s = a % p + b % p + carry;
2060 carry = u128::from(s >= p);
2061 count += carry as u64;
2062 a /= p;
2063 b /= p;
2064 }
2065 count
2066}
2067
2068fn vp_factorial(n: u64, p: u64) -> u64 {
2070 let mut s = 0u64;
2071 let mut pk = p;
2072 while pk <= n {
2073 s += n / pk;
2074 pk = pk.saturating_mul(p);
2075 }
2076 s
2077}
2078
2079fn vp_binom(n: u64, k: u64, p: u64) -> u64 {
2081 vp_factorial(n, p) - vp_factorial(k, p) - vp_factorial(n - k, p)
2082}
2083
2084fn vp_of(mut n: u64, p: u64) -> u64 {
2086 let mut v = 0u64;
2087 while n.is_multiple_of(p) {
2088 n /= p;
2089 v += 1;
2090 }
2091 v
2092}
2093
2094fn gcd_u64(mut a: u64, mut b: u64) -> u64 {
2095 while b != 0 {
2096 let t = a % b;
2097 a = b;
2098 b = t;
2099 }
2100 a
2101}
2102
2103fn primes_upto(n: u64) -> Vec<u64> {
2105 (2..=n).filter(|&q| is_prime(q)).collect()
2106}
2107
2108fn parse_decimal_u128(s: &str) -> Result<u128, String> {
2110 if s.is_empty() || s.len() > 38 || !s.bytes().all(|b| b.is_ascii_digit()) {
2111 return Err(format!("`{s}` is not a 1..=38 digit decimal string"));
2112 }
2113 s.parse::<u128>().map_err(|e| format!("parse `{s}`: {e}"))
2114}
2115
2116fn decimal_mod(s: &str, m: u64) -> Result<u64, String> {
2119 if s.is_empty() || !s.bytes().all(|b| b.is_ascii_digit()) {
2120 return Err(format!("`{s}` is not a decimal string"));
2121 }
2122 let mut acc: u64 = 0;
2123 for b in s.bytes() {
2124 acc = (acc * 10 + u64::from(b - b'0')) % m;
2125 }
2126 Ok(acc)
2127}
2128
2129fn multiplicative_order(base: u64, p: u64) -> Result<u64, String> {
2132 if base.is_multiple_of(p) {
2133 return Err(format!("{base} is 0 mod {p}; order undefined"));
2134 }
2135 let mut acc = base % p;
2136 let mut ord = 1u64;
2137 while acc != 1 {
2138 acc = acc * base % p;
2139 ord += 1;
2140 if ord >= p {
2141 return Err(format!("order of {base} mod {p} did not divide p-1"));
2142 }
2143 }
2144 Ok(ord)
2145}
2146
2147pub fn verify_crt_partial_cover(m: &str, rows: &[CrtCoverRow]) -> VerifyResult {
2156 if rows.is_empty() {
2157 return VerifyResult::fail("need at least one prime row");
2158 }
2159 match (decimal_mod(m, 2), decimal_mod(m, 3)) {
2160 (Ok(r2), Ok(r3)) => {
2161 if r2 == 0 || r3 == 0 {
2162 return VerifyResult::fail("m must be coprime to 6");
2163 }
2164 }
2165 (Err(e), _) | (_, Err(e)) => return VerifyResult::fail(e),
2166 }
2167 for row in rows {
2168 let p = row.p;
2169 if !(5..=1_000_000).contains(&p) || !is_prime(p) {
2170 return VerifyResult::fail(format!("row p={p} must be a prime in [5, 10^6]"));
2171 }
2172 let ord2 = match multiplicative_order(2, p) {
2173 Ok(v) => v,
2174 Err(e) => return VerifyResult::fail(e),
2175 };
2176 let ord3 = match multiplicative_order(3, p) {
2177 Ok(v) => v,
2178 Err(e) => return VerifyResult::fail(e),
2179 };
2180 if ord2 != row.ord2 || ord3 != row.ord3 {
2181 return VerifyResult::fail(format!(
2182 "row p={p}: ord(2)={ord2}, ord(3)={ord3} != claimed ({}, {})",
2183 row.ord2, row.ord3
2184 ));
2185 }
2186 let h = ord2 / gcd_u64(ord2, ord3) * ord3;
2187 if h != row.h || row.line[3] != h {
2188 return VerifyResult::fail(format!(
2189 "row p={p}: lcm(ord2, ord3)={h} != claimed h={} / line modulus {}",
2190 row.h, row.line[3]
2191 ));
2192 }
2193 if h > 5_000 {
2194 return VerifyResult::fail(format!("row p={p}: h={h} exceeds the 5000 guard"));
2195 }
2196 let mm = match decimal_mod(m, p) {
2197 Ok(v) => v,
2198 Err(e) => return VerifyResult::fail(e),
2199 };
2200 if mm != row.m_mod_p || mm == 0 {
2201 return VerifyResult::fail(format!(
2202 "row p={p}: m mod p = {mm} != claimed {} (and must be nonzero)",
2203 row.m_mod_p
2204 ));
2205 }
2206 let t = (p - mod_pow(mm, p - 2, p)) % p;
2207 if t != row.t_p {
2208 return VerifyResult::fail(format!(
2209 "row p={p}: (-m^-1) mod p = {t} != claimed t_p={}",
2210 row.t_p
2211 ));
2212 }
2213 let (al, be, ga) = (row.line[0], row.line[1], row.line[2]);
2214 for k in 0..h {
2215 for l in 0..h {
2216 let lhs = (mod_pow(2, k, p) * mod_pow(3, l, p) % p * mm % p + 1).is_multiple_of(p);
2217 let rhs = (al * k + be * l) % h == ga % h; if lhs != rhs {
2219 return VerifyResult::fail(format!(
2220 "row p={p}: congruence line fails at (k, l) = ({k}, {l})"
2221 ));
2222 }
2223 }
2224 }
2225 }
2226 VerifyResult::ok(format!(
2227 "Erdos #203 partial CRT cover: m coprime to 6, {} prime row(s) verified (p | 2^k 3^l m + 1 <=> affine line mod h)",
2228 rows.len()
2229 ))
2230}
2231
2232pub fn verify_kummer_no_carry(entries: &[KummerEntry]) -> VerifyResult {
2239 if entries.is_empty() {
2240 return VerifyResult::fail("need at least one (k, m) entry");
2241 }
2242 for e in entries {
2243 let k = e.k;
2244 if !(3..=20).contains(&k) {
2245 return VerifyResult::fail(format!("k={k} outside the [3, 20] guard"));
2246 }
2247 let mut m: u64 = 1;
2248 for p in primes_upto(k) {
2249 let mut pe = 1u64;
2250 let mut exp = 0u64;
2251 while pe * p <= k {
2252 pe *= p;
2253 exp += 1;
2254 }
2255 for _ in 0..=exp {
2256 m = match m.checked_mul(p) {
2257 Some(v) => v,
2258 None => return VerifyResult::fail(format!("M_{k} overflows u64")),
2259 };
2260 }
2261 }
2262 if m != e.m {
2263 return VerifyResult::fail(format!("k={k}: recomputed M_k={m} != claimed {}", e.m));
2264 }
2265 let n = m - 1;
2266 for j in 2..=k {
2267 for p in primes_upto(j) {
2268 if carries_base_p(u128::from(j), u128::from(n - j), u128::from(p)) != 0 {
2269 return VerifyResult::fail(format!(
2270 "k={k}: carry adding {j} + (M-1-{j}) base {p} — C(M-1, {j}) not p-free"
2271 ));
2272 }
2273 }
2274 }
2275 }
2276 VerifyResult::ok(format!(
2277 "Erdos #684 certificate: f(M_k - 1) > k verified for {} value(s) of k (zero Kummer carries)",
2278 entries.len()
2279 ))
2280}
2281
2282pub fn verify_min_binom_gcd(cases: &[MinGcdCase]) -> VerifyResult {
2288 if cases.is_empty() {
2289 return VerifyResult::fail("need at least one (n, f) case");
2290 }
2291 for c in cases {
2292 let n = c.n;
2293 if !(4..=10_000).contains(&n) {
2294 return VerifyResult::fail(format!("n={n} outside the [4, 10000] guard"));
2295 }
2296 let mut factors: Vec<(u64, u64)> = Vec::new();
2297 let mut rem = n;
2298 let mut p = 2u64;
2299 while p * p <= rem {
2300 if rem.is_multiple_of(p) {
2301 factors.push((p, vp_of(rem, p)));
2302 while rem.is_multiple_of(p) {
2303 rem /= p;
2304 }
2305 }
2306 p += 1;
2307 }
2308 if rem > 1 {
2309 factors.push((rem, 1));
2310 }
2311 let mut best = u64::MAX;
2312 for k in 2..=n / 2 {
2313 let mut g = 1u64;
2314 for &(p, vn) in &factors {
2315 let carries = carries_base_p(u128::from(k), u128::from(n - k), u128::from(p));
2316 g *= p.pow(vn.min(carries) as u32);
2317 }
2318 best = best.min(g);
2319 }
2320 if best != c.f {
2321 return VerifyResult::fail(format!("n={n}: recomputed f(n)={best} != claimed {}", c.f));
2322 }
2323 }
2324 VerifyResult::ok(format!(
2325 "Erdos #700 certificate: f(n) = min gcd(n, C(n,k)) verified for {} case(s)",
2326 cases.len()
2327 ))
2328}
2329
2330fn divides_smooth(mut x: u128, i: u64, k: u64) -> bool {
2337 for p in primes_upto(k) {
2338 if x == 1 {
2339 break;
2340 }
2341 let pp = u128::from(p);
2342 let mut e = 0u64;
2343 while x.is_multiple_of(pp) {
2344 x /= pp;
2345 e += 1;
2346 }
2347 if e > 0 && vp_of(i, p) + vp_binom(k, i, p) < e {
2348 return false;
2349 }
2350 }
2351 x == 1
2352}
2353
2354pub fn verify_binom_deficiency(entries: &[DeficiencyEntry]) -> VerifyResult {
2358 if entries.is_empty() {
2359 return VerifyResult::fail("need at least one entry");
2360 }
2361 for e in entries {
2362 let k = e.k;
2363 if !(2..=150).contains(&k) {
2364 return VerifyResult::fail(format!("k={k} outside the [2, 150] guard"));
2365 }
2366 let n = match parse_decimal_u128(&e.n) {
2367 Ok(v) => v,
2368 Err(err) => return VerifyResult::fail(err),
2369 };
2370 if n < 2 * u128::from(k) {
2371 return VerifyResult::fail(format!("entry k={k}: need N >= 2k"));
2372 }
2373 for p in primes_upto(k) {
2374 if carries_base_p(u128::from(k), n - u128::from(k), u128::from(p)) != 0 {
2375 return VerifyResult::fail(format!(
2376 "entry k={k}: prime {p} divides C(N,k) — not Kummer-defined"
2377 ));
2378 }
2379 }
2380 let mut slots: Vec<u64> = Vec::new();
2381 for i in 1..=k {
2382 let x = n - u128::from(k) + u128::from(i);
2383 if divides_smooth(x, i, k) {
2384 slots.push(i);
2385 }
2386 }
2387 if slots.len() as u64 != e.delta {
2388 return VerifyResult::fail(format!(
2389 "entry k={k}: recomputed delta={} != claimed {}",
2390 slots.len(),
2391 e.delta
2392 ));
2393 }
2394 if let Some(claimed) = &e.slots
2395 && &slots != claimed
2396 {
2397 return VerifyResult::fail(format!(
2398 "entry k={k}: smooth slots {slots:?} != claimed {claimed:?}"
2399 ));
2400 }
2401 }
2402 VerifyResult::ok(format!(
2403 "Erdos #1093 deficiency certificate: {} entr(ies) Kummer-defined with delta and slots recomputed exactly",
2404 entries.len()
2405 ))
2406}
2407
2408fn binom_u64(k: u64, r: u64) -> u64 {
2412 let r = r.min(k - r);
2413 let mut res = 1u64;
2414 for i in 1..=r {
2415 res = res * (k - r + i) / i;
2416 }
2417 res
2418}
2419
2420fn divisors_smooth(g: u64, k: u64) -> Option<Vec<u64>> {
2424 let mut rem = g;
2425 let mut pf: Vec<(u64, u64)> = Vec::new();
2426 for p in primes_upto(k) {
2427 if rem.is_multiple_of(p) {
2428 pf.push((p, vp_of(rem, p)));
2429 while rem.is_multiple_of(p) {
2430 rem /= p;
2431 }
2432 }
2433 }
2434 if rem != 1 {
2435 return None;
2436 }
2437 let mut divs: Vec<u64> = vec![1];
2438 for (p, e) in pf {
2439 let prev = divs.clone();
2440 let mut pe = 1u64;
2441 for _ in 0..e {
2442 pe *= p;
2443 for d in &prev {
2444 divs.push(d * pe);
2445 }
2446 }
2447 if divs.len() > 200_000 {
2448 return None;
2449 }
2450 }
2451 Some(divs)
2452}
2453
2454fn is_exception_guarded(n: u64, k: u64) -> Option<bool> {
2460 let mut p = 2u64;
2461 while p <= k || p.saturating_mul(k) <= n {
2463 if is_prime(p) && vp_binom(n, k, p) > 0 {
2464 return Some(false);
2465 }
2466 if p > 10_000_000 {
2467 return None;
2468 }
2469 p += 1;
2470 }
2471 Some(true)
2472}
2473
2474pub fn verify_binom_exception_enum(k_max: u64, exceptions: &[(u64, u64)]) -> VerifyResult {
2479 if !(3..=40).contains(&k_max) {
2480 return VerifyResult::fail(format!("k_max={k_max} outside the [3, 40] guard"));
2481 }
2482 let claimed: std::collections::BTreeSet<(u64, u64)> = exceptions.iter().copied().collect();
2483 for &(n, k) in &claimed {
2484 if k > k_max || n < 2 * k {
2485 return VerifyResult::fail(format!(
2486 "claimed exception (N={n}, k={k}) outside k <= k_max / N >= 2k"
2487 ));
2488 }
2489 }
2490 let mut found: std::collections::BTreeSet<(u64, u64)> = std::collections::BTreeSet::new();
2491 let mut lambda: u64 = 1;
2492 let mut candidates: u64 = 0;
2493 for k in 2..=k_max {
2494 lambda = lambda / gcd_u64(lambda, k) * k;
2495 for r in 1..=k {
2496 let g = gcd_u64(lambda, r * binom_u64(k, r));
2497 let divs = match divisors_smooth(g, k) {
2498 Some(d) => d,
2499 None => {
2500 return VerifyResult::fail(format!(
2501 "divisor enumeration guard exceeded at k={k}, r={r}"
2502 ));
2503 }
2504 };
2505 for x in divs {
2506 if !x.is_multiple_of(k) {
2507 continue;
2508 }
2509 let n = x + k - r;
2510 if n < 2 * k {
2511 continue;
2512 }
2513 candidates += 1;
2514 match is_exception_guarded(n, k) {
2515 Some(true) => {
2516 found.insert((n, k));
2517 }
2518 Some(false) => {}
2519 None => {
2520 return VerifyResult::fail(format!(
2521 "exception test guard exceeded at (N={n}, k={k}) — refusing to claim"
2522 ));
2523 }
2524 }
2525 }
2526 }
2527 }
2528 if found != claimed {
2529 let extra: Vec<_> = found.difference(&claimed).collect();
2530 let missing: Vec<_> = claimed.difference(&found).collect();
2531 return VerifyResult::fail(format!(
2532 "exception set mismatch: extra {extra:?}, missing {missing:?}"
2533 ));
2534 }
2535 VerifyResult::ok(format!(
2536 "Erdos #1094 enumeration: {candidates} candidate(s) checked for k <= {k_max}; exception set of {} matches exactly",
2537 claimed.len()
2538 ))
2539}
2540
2541fn rat_check(step: &LratStep, db: &std::collections::HashMap<u64, Vec<i64>>) -> bool {
2555 let Some(&pivot) = step.literals.first() else {
2556 return false; };
2558 let supplied: std::collections::HashMap<u64, &Vec<u64>> =
2559 step.rat_hints.iter().map(|(id, h)| (*id, h)).collect();
2560 for (&cid, clause) in db {
2561 if !clause.contains(&-pivot) {
2562 continue;
2563 }
2564 let mut resolvent: Vec<i64> = step.literals.clone();
2565 for &l in clause {
2566 if l != -pivot && l != 0 && !resolvent.contains(&l) {
2567 resolvent.push(l);
2568 }
2569 }
2570 if resolvent.iter().any(|&l| resolvent.contains(&-l) && l > 0) {
2571 continue; }
2573 let Some(hints) = supplied.get(&cid) else {
2574 return false;
2575 };
2576 if !rup_checks(&resolvent, hints, db) {
2577 return false;
2578 }
2579 }
2580 true
2581}
2582
2583fn rup_checks(c: &[i64], hints: &[u64], db: &std::collections::HashMap<u64, Vec<i64>>) -> bool {
2584 let mut assign: std::collections::HashMap<i64, bool> = std::collections::HashMap::new();
2586 for &l in c {
2587 if l == 0 {
2588 return false;
2589 }
2590 let v = l.abs();
2591 let want = l < 0; if let Some(&prev) = assign.get(&v)
2593 && prev != want
2594 {
2595 return false; }
2597 assign.insert(v, want);
2598 }
2599 for &h in hints {
2600 let Some(cl) = db.get(&h) else {
2601 return false; };
2603 let mut unassigned: Vec<i64> = Vec::new();
2604 let mut satisfied = false;
2605 for &l in cl {
2606 if l == 0 {
2607 continue;
2608 }
2609 match assign.get(&l.abs()) {
2610 None => unassigned.push(l),
2611 Some(&val) => {
2612 if (l > 0) == val {
2614 satisfied = true;
2615 }
2616 }
2617 }
2618 }
2619 if satisfied {
2620 return false; }
2622 match unassigned.len() {
2623 0 => return true, 1 => {
2625 let l = unassigned[0];
2626 assign.insert(l.abs(), l > 0); }
2628 _ => return false, }
2630 }
2631 false }
2633
2634pub fn verify_unsat_cert(cnf: &[Vec<i64>], proof: &[LratStep]) -> VerifyResult {
2639 if cnf.is_empty() {
2640 return VerifyResult::fail("empty CNF: nothing to refute");
2641 }
2642 if cnf.len() > 5_000_000 || proof.len() > 20_000_000 {
2643 return VerifyResult::fail("certificate exceeds the size guard");
2644 }
2645 let mut db: std::collections::HashMap<u64, Vec<i64>> = std::collections::HashMap::new();
2646 for (i, clause) in cnf.iter().enumerate() {
2647 let id = (i + 1) as u64; if db.insert(id, clause.clone()).is_some() {
2649 return VerifyResult::fail(format!("duplicate clause id {id}"));
2650 }
2651 }
2652 let mut derived_empty = false;
2653 for step in proof {
2654 if step.id == 0 {
2655 return VerifyResult::fail("proof clause id 0 is reserved");
2656 }
2657 if !rup_checks(&step.literals, &step.hints, &db) && !rat_check(step, &db) {
2658 return VerifyResult::fail(format!(
2659 "LRAT step {} is neither RUP-implied nor RAT on its first literal",
2660 step.id
2661 ));
2662 }
2663 let empty = step.literals.is_empty();
2664 if db.insert(step.id, step.literals.clone()).is_some() {
2665 return VerifyResult::fail(format!("clause id {} added twice", step.id));
2666 }
2667 if empty {
2668 derived_empty = true;
2669 break;
2670 }
2671 }
2672 if !derived_empty {
2673 return VerifyResult::fail("proof never derives the empty clause (UNSAT not established)");
2674 }
2675 VerifyResult::ok(format!(
2676 "UNSAT certificate: {} clause(s), {} LRAT step(s), empty clause derived by RUP",
2677 cnf.len(),
2678 proof.len()
2679 ))
2680}
2681
2682pub fn verify_golomb(marks: &[i64]) -> VerifyResult {
2683 let set: HashSet<&i64> = marks.iter().collect();
2684 if set.len() != marks.len() {
2685 return VerifyResult::fail("duplicate marks");
2686 }
2687 let mut diffs: HashSet<i64> = HashSet::new();
2688 let mut count = 0usize;
2689 for i in 0..marks.len() {
2690 for j in (i + 1)..marks.len() {
2691 if !diffs.insert((marks[j] - marks[i]).abs()) {
2692 return VerifyResult::fail("repeated pairwise difference (not a Golomb ruler)");
2693 }
2694 count += 1;
2695 }
2696 }
2697 let (lo, hi) = (marks.iter().min().copied(), marks.iter().max().copied());
2698 let length = match (lo, hi) {
2699 (Some(a), Some(b)) => b - a,
2700 _ => 0,
2701 };
2702 VerifyResult::ok(format!(
2703 "Golomb ruler: {} marks, length {length}, all {count} differences distinct",
2704 marks.len()
2705 ))
2706}
2707
2708pub fn verify_cap(points: &[Vec<i64>], n: usize) -> VerifyResult {
2711 let set: HashSet<&Vec<i64>> = points.iter().collect();
2712 if set.len() != points.len() {
2713 return VerifyResult::fail("duplicate points");
2714 }
2715 if !points
2716 .iter()
2717 .all(|p| p.len() == n && p.iter().all(|&x| (0..=2).contains(&x)))
2718 {
2719 return VerifyResult::fail(format!("points not in (0,1,2)^{n}"));
2720 }
2721 let owned: HashSet<Vec<i64>> = points.iter().cloned().collect();
2722 let m = points.len();
2723 for i in 0..m {
2724 let a = &points[i];
2725 for b in points.iter().take(m).skip(i + 1) {
2726 let c: Vec<i64> = (0..n).map(|k| (-(a[k] + b[k])).rem_euclid(3)).collect();
2727 if owned.contains(&c) && &c != a && &c != b {
2728 return VerifyResult::fail("3 collinear points found (not a cap)");
2729 }
2730 }
2731 }
2732 VerifyResult::ok(format!(
2733 "cap verified: {m} points in F_3^{n}, no 3 collinear"
2734 ))
2735}
2736
2737pub fn verify_bh(points: &[Vec<i64>], n: usize, h: usize) -> VerifyResult {
2740 if let Some(bad) = binary_points_ok(points, n) {
2741 return bad;
2742 }
2743 let m = points.len();
2744 if m == 0 || h == 0 {
2745 return VerifyResult::ok(format!("B_{h} verified: {m} points, 0 sums"));
2746 }
2747 let mut sums: HashSet<Vec<i64>> = HashSet::new();
2748 let mut count = 0usize;
2749 let mut idx = vec![0usize; h];
2750 loop {
2751 let mut s = vec![0i64; n];
2752 for &i in &idx {
2753 for k in 0..n {
2754 s[k] += points[i][k];
2755 }
2756 }
2757 if !sums.insert(s) {
2758 return VerifyResult::fail(format!("B_{h} violated: a repeated {h}-fold sum"));
2759 }
2760 count += 1;
2761 if !advance_with_replacement(&mut idx, m) {
2762 break;
2763 }
2764 }
2765 VerifyResult::ok(format!(
2766 "B_{h} verified: {m} points, {count} h-fold sums all distinct"
2767 ))
2768}
2769
2770pub fn verify_covering(blocks: &[Vec<usize>], v: usize, k: usize, t: usize) -> VerifyResult {
2773 let norm: Vec<Vec<usize>> = blocks
2774 .iter()
2775 .map(|b| {
2776 let s: std::collections::BTreeSet<usize> = b.iter().copied().collect();
2777 s.into_iter().collect()
2778 })
2779 .collect();
2780 if !norm
2781 .iter()
2782 .all(|b| b.len() == k && b.iter().all(|&x| x < v))
2783 {
2784 return VerifyResult::fail(format!("blocks not valid {k}-subsets of [0,{v})"));
2785 }
2786 let mut covered: HashSet<Vec<usize>> = HashSet::new();
2787 for b in &norm {
2788 each_combination(b.len(), t, &mut |sub| {
2789 covered.insert(sub.iter().map(|&i| b[i]).collect());
2790 });
2791 }
2792 let mut need = 0usize;
2793 let mut missing = 0usize;
2794 each_combination(v, t, &mut |sub| {
2795 need += 1;
2796 if !covered.contains(sub) {
2797 missing += 1;
2798 }
2799 });
2800 if missing > 0 {
2801 return VerifyResult::fail(format!(
2802 "not a covering: {missing} of {need} t-subsets uncovered"
2803 ));
2804 }
2805 VerifyResult::ok(format!(
2806 "valid C({v},{k},{t}) covering with {} blocks",
2807 norm.len()
2808 ))
2809}
2810
2811pub fn verify_constant_weight(words: &[Vec<i64>], n: usize, d: usize, w: usize) -> VerifyResult {
2814 let set: HashSet<&Vec<i64>> = words.iter().collect();
2815 if set.len() != words.len() {
2816 return VerifyResult::fail("duplicate codewords");
2817 }
2818 if !words
2819 .iter()
2820 .all(|c| c.len() == n && c.iter().all(|&x| x == 0 || x == 1))
2821 {
2822 return VerifyResult::fail(format!("words not binary length-{n}"));
2823 }
2824 if let Some(c) = words.iter().find(|c| c.iter().sum::<i64>() as usize != w) {
2825 return VerifyResult::fail(format!(
2826 "a codeword has weight {} != {w}",
2827 c.iter().sum::<i64>()
2828 ));
2829 }
2830 for i in 0..words.len() {
2831 for j in (i + 1)..words.len() {
2832 let dist = (0..n).filter(|&k| words[i][k] != words[j][k]).count();
2833 if dist < d {
2834 return VerifyResult::fail(format!("a pair has Hamming distance {dist} < {d}"));
2835 }
2836 }
2837 }
2838 VerifyResult::ok(format!(
2839 "constant-weight code A({n},{d},{w}): {} words, all weight {w}, min dist >= {d}",
2840 words.len()
2841 ))
2842}
2843
2844pub fn verify_costas(perm: &[i64]) -> VerifyResult {
2847 let n = perm.len();
2848 let mut sorted = perm.to_vec();
2849 sorted.sort_unstable();
2850 let min = perm.iter().min().copied().unwrap_or(0);
2851 let expected: Vec<i64> = (0..n as i64).map(|i| min + i).collect();
2852 if sorted != expected {
2853 return VerifyResult::fail("not a permutation");
2854 }
2855 let mut vecs: HashSet<(i64, i64)> = HashSet::new();
2856 let mut count = 0usize;
2857 for i in 0..n {
2858 for j in (i + 1)..n {
2859 if !vecs.insert(((j - i) as i64, perm[j] - perm[i])) {
2860 return VerifyResult::fail("repeated displacement vector (not a Costas array)");
2861 }
2862 count += 1;
2863 }
2864 }
2865 VerifyResult::ok(format!(
2866 "Costas array of order {n} verified ({count} displacement vectors all distinct)"
2867 ))
2868}
2869
2870#[allow(clippy::needless_range_loop)]
2879pub fn verify_linear_code(generator: &[Vec<i64>], q: u64, claimed_d: usize) -> VerifyResult {
2880 const MAX_ENUM: u64 = 1_000_000;
2881 if !is_prime(q) {
2882 return VerifyResult::fail(format!(
2883 "q={q} not prime; prime-power GF(q) not implemented — refusing to claim"
2884 ));
2885 }
2886 let k = generator.len();
2887 if k == 0 {
2888 return VerifyResult::fail("empty generator");
2889 }
2890 let n = generator[0].len();
2891 if !generator.iter().all(|row| row.len() == n) {
2892 return VerifyResult::fail("ragged generator matrix");
2893 }
2894 let g: Vec<Vec<u64>> = generator
2895 .iter()
2896 .map(|row| row.iter().map(|&x| x.rem_euclid(q as i64) as u64).collect())
2897 .collect();
2898 if gf_rank(&g, q) != k {
2899 return VerifyResult::fail(format!(
2900 "generator rank < k={k} (rows dependent — not an [n,{k}] code)"
2901 ));
2902 }
2903 let qk = (q).checked_pow(k as u32);
2904 match qk {
2905 Some(v) if v <= MAX_ENUM => {}
2906 _ => {
2907 return VerifyResult::fail(format!(
2908 "q^k exceeds enum guard {MAX_ENUM}; distance not exhaustively verifiable — refusing to claim"
2909 ));
2910 }
2911 }
2912 let qk = qk.unwrap();
2913 let mut dmin = n + 1;
2914 let mut msg = vec![0u64; k];
2916 for code in 1..qk {
2917 let mut x = code;
2919 for m in msg.iter_mut() {
2920 *m = x % q;
2921 x /= q;
2922 }
2923 let mut weight = 0usize;
2924 for c in 0..n {
2925 let mut s = 0u64;
2926 for i in 0..k {
2927 if msg[i] != 0 {
2928 s = (s + msg[i] * g[i][c]) % q;
2929 }
2930 }
2931 if s != 0 {
2932 weight += 1;
2933 }
2934 }
2935 if weight < dmin {
2936 dmin = weight;
2937 }
2938 }
2939 let ok = dmin >= claimed_d;
2940 let rel = if ok { ">=" } else { "<" };
2941 VerifyResult {
2942 ok,
2943 message: format!(
2944 "[{n},{k},{dmin}]_{q} verified (min weight {dmin} {rel} claimed {claimed_d})"
2945 ),
2946 value: Some(dmin as f64),
2947 }
2948}
2949
2950fn advance_with_replacement(idx: &mut [usize], m: usize) -> bool {
2955 let h = idx.len();
2956 let mut i = h;
2957 loop {
2958 if i == 0 {
2959 return false;
2960 }
2961 i -= 1;
2962 if idx[i] != m - 1 {
2963 let nv = idx[i] + 1;
2964 for slot in idx.iter_mut().take(h).skip(i) {
2965 *slot = nv;
2966 }
2967 return true;
2968 }
2969 }
2970}
2971
2972fn each_combination(n: usize, t: usize, f: &mut impl FnMut(&[usize])) {
2975 if t > n {
2976 return;
2977 }
2978 let mut idx: Vec<usize> = (0..t).collect();
2979 loop {
2980 f(&idx);
2981 let mut i = t;
2983 loop {
2984 if i == 0 {
2985 return;
2986 }
2987 i -= 1;
2988 if idx[i] != i + n - t {
2989 idx[i] += 1;
2990 for j in (i + 1)..t {
2991 idx[j] = idx[j - 1] + 1;
2992 }
2993 break;
2994 }
2995 }
2996 }
2997}
2998
2999fn is_prime(q: u64) -> bool {
3000 if q < 2 {
3001 return false;
3002 }
3003 let mut p = 2u64;
3004 while p * p <= q {
3005 if q.is_multiple_of(p) {
3006 return false;
3007 }
3008 p += 1;
3009 }
3010 true
3011}
3012
3013#[allow(clippy::needless_range_loop)]
3018fn gf_rank(rows: &[Vec<u64>], q: u64) -> usize {
3019 let mut m: Vec<Vec<u64>> = rows.to_vec();
3020 if m.is_empty() {
3021 return 0;
3022 }
3023 let ncols = m[0].len();
3024 let mut rank = 0usize;
3025 for col in 0..ncols {
3026 let piv = (rank..m.len()).find(|&r| !m[r][col].is_multiple_of(q));
3027 let Some(piv) = piv else { continue };
3028 m.swap(rank, piv);
3029 let inv = mod_inv(m[rank][col] % q, q);
3030 for c in 0..ncols {
3031 m[rank][c] = (m[rank][c] * inv) % q;
3032 }
3033 for r in 0..m.len() {
3034 if r != rank && !m[r][col].is_multiple_of(q) {
3035 let f = m[r][col] % q;
3036 for c in 0..ncols {
3037 m[r][c] = (m[r][c] + q - (f * m[rank][c]) % q) % q;
3038 }
3039 }
3040 }
3041 rank += 1;
3042 if rank == m.len() {
3043 break;
3044 }
3045 }
3046 rank
3047}
3048
3049fn mod_inv(a: u64, q: u64) -> u64 {
3051 mod_pow(a, q - 2, q)
3052}
3053
3054fn mod_pow(mut base: u64, mut exp: u64, modulus: u64) -> u64 {
3055 let mut result = 1u64;
3056 base %= modulus;
3057 while exp > 0 {
3058 if exp & 1 == 1 {
3059 result = (result * base) % modulus;
3060 }
3061 exp >>= 1;
3062 base = (base * base) % modulus;
3063 }
3064 result
3065}
3066
3067#[cfg(test)]
3068mod tests {
3069 use super::*;
3070
3071 fn small_sidon() -> Vec<Vec<i64>> {
3074 vec![vec![0, 0, 0], vec![1, 0, 0], vec![0, 1, 0], vec![0, 0, 1]]
3078 }
3079
3080 #[test]
3083 fn faithful_parses_real_a309370_assertion() {
3084 let text = "OEIS A309370 a(20) >= 1989: a Sidon set of 1989 distinct binary \
3085 vectors in {0,1}^20 under componentwise integer addition, with all \
3086 pairwise sums distinct. Frozen-verified by vela-verify (sidon kind).";
3087 let p = parse_claim(text).expect("should parse the canonical A309370 form");
3088 assert_eq!(p.kind, "sidon");
3089 assert_eq!(p.ambient_n, Some(20));
3090 assert_eq!(p.bound, 1989);
3091 assert!(!p.exact);
3092 }
3093
3094 #[test]
3095 fn faithful_happy_path() {
3096 let text = "a(3) >= 4: a Sidon set of 4 vectors in {0,1}^3.";
3097 let w = Witness::Sidon {
3098 n: 3,
3099 points: small_sidon(),
3100 claimed_size: Some(4),
3101 };
3102 let f = claim_witness_faithful(text, &w);
3103 assert!(f.faithful, "{:?}", f.reasons);
3104 }
3105
3106 #[test]
3109 fn faithful_rejects_inflated_lower_bound() {
3110 let text = "a(3) >= 5: a Sidon set of 5 vectors in {0,1}^3.";
3111 let w = Witness::Sidon {
3112 n: 3,
3113 points: small_sidon(), claimed_size: None,
3115 };
3116 assert!(verify_witness(&w).ok, "the witness itself is valid");
3117 let f = claim_witness_faithful(text, &w);
3118 assert!(!f.faithful);
3119 assert!(f.reasons.iter().any(|r| r.contains("does not establish")));
3120 }
3121
3122 #[test]
3124 fn faithful_rejects_dimension_mismatch() {
3125 let text = "a(8) >= 4: a Sidon set of 4 vectors in {0,1}^8.";
3126 let w = Witness::Sidon {
3127 n: 3,
3128 points: small_sidon(),
3129 claimed_size: None,
3130 };
3131 let f = claim_witness_faithful(text, &w);
3132 assert!(!f.faithful);
3133 assert!(f.reasons.iter().any(|r| r.contains("dimension")));
3134 }
3135
3136 #[test]
3138 fn faithful_rejects_kind_mismatch() {
3139 let text = "an optimal Golomb ruler of order 4 with >= 4 marks.";
3140 let w = Witness::Sidon {
3141 n: 3,
3142 points: small_sidon(),
3143 claimed_size: None,
3144 };
3145 let f = claim_witness_faithful(text, &w);
3146 assert!(!f.faithful);
3147 assert!(f.reasons.iter().any(|r| r.contains("kind")));
3148 }
3149
3150 #[test]
3152 fn faithful_rejects_invalid_witness() {
3153 let text = "a(3) >= 4: a Sidon set of 4 vectors in {0,1}^3.";
3154 let w = Witness::Sidon {
3156 n: 3,
3157 points: vec![vec![0, 0, 0], vec![1, 0, 0], vec![1, 0, 0], vec![0, 1, 0]],
3158 claimed_size: None,
3159 };
3160 let f = claim_witness_faithful(text, &w);
3161 assert!(!f.faithful);
3162 assert!(f.reasons.iter().any(|r| r.contains("does not verify")));
3163 }
3164
3165 #[test]
3168 fn faithful_refuses_unparseable_asymptotic_claim() {
3169 let text = "Singer's perfect-difference-set construction yields Sidon sets in \
3170 {1,...,N} of size sqrt(N) + O(N^{1/4}).";
3171 let w = Witness::Sidon {
3172 n: 3,
3173 points: small_sidon(),
3174 claimed_size: None,
3175 };
3176 let f = claim_witness_faithful(text, &w);
3177 assert!(!f.faithful);
3178 assert!(f.parsed.is_none());
3179 }
3180
3181 #[test]
3183 fn faithful_refuses_ambiguous_bound() {
3184 let text = "a Sidon set in {0,1}^3 with >= 4 and exactly 5 elements.";
3185 assert!(parse_claim(text).is_none());
3186 }
3187
3188 #[test]
3189 fn faithful_routes_equality_optimality_to_review() {
3190 let w = Witness::Sidon {
3198 n: 3,
3199 points: small_sidon(), claimed_size: None,
3201 };
3202 let f = claim_witness_faithful("a Sidon set in {0,1}^3 with exactly 4 elements.", &w);
3203 assert!(
3204 !f.faithful,
3205 "equality/optimality is not witness-establishable"
3206 );
3207 assert!(f.reasons.iter().any(|r| r.contains("equality/optimality")));
3208 let f2 = claim_witness_faithful("Sidon a(3) = 4 in {0,1}^3 (new record).", &w);
3210 assert!(!f2.faithful, "a `= N` headline also routes to review");
3211 }
3212
3213 #[test]
3220 fn faithful_binds_a_of_n_order_to_witness() {
3221 let w = Witness::Sidon {
3222 n: 3,
3223 points: small_sidon(),
3224 claimed_size: None,
3225 }; assert!(verify_witness(&w).ok, "the witness itself is valid");
3227 let f = claim_witness_faithful("Sidon record a(20): at least 4 points.", &w);
3229 assert!(
3230 !f.faithful,
3231 "an a(20) claim cannot ride an n=3 witness: {:?}",
3232 f.reasons
3233 );
3234 let f2 = claim_witness_faithful("A Sidon set, at least 4 points, beats the record.", &w);
3236 assert!(
3237 !f2.faithful,
3238 "a dimensioned claim with no ambient routes to review: {:?}",
3239 f2.reasons
3240 );
3241 }
3242
3243 #[test]
3246 fn faithful_rejects_dual_bound_headline() {
3247 let w = Witness::Sidon {
3248 n: 3,
3249 points: small_sidon(),
3250 claimed_size: None,
3251 };
3252 let f = claim_witness_faithful(
3253 "Sidon in {0,1}^3: a(3) = 2500 (beats prior 1989). The witness has at least 4 points.",
3254 &w,
3255 );
3256 assert!(
3257 !f.faithful,
3258 "a `= headline` beside an `at least` clause is ambiguous: {:?}",
3259 f.reasons
3260 );
3261 assert!(
3262 f.parsed.is_none(),
3263 "the dual lower+equality marker fails parse"
3264 );
3265 }
3266
3267 #[test]
3270 fn faithful_gf2_binds_dimension() {
3271 let good = Witness::Gf2Sidon {
3272 elements: vec![1, 2, 4],
3273 claimed_size: None,
3274 };
3275 assert!(verify_witness(&good).ok);
3276 let f = claim_witness_faithful("OEIS A394031 a(3) >= 3: a Sidon set in GF(2)^3.", &good);
3277 assert!(f.faithful, "genuine GF(2)^3 claim: {:?}", f.reasons);
3278
3279 let wide = Witness::Gf2Sidon {
3280 elements: vec![1, 2, 4, 8, 16],
3281 claimed_size: None,
3282 };
3283 assert!(
3284 verify_witness(&wide).ok,
3285 "the wider witness is itself valid"
3286 );
3287 let f2 = claim_witness_faithful("OEIS A394031 a(4) >= 5: a Sidon set in GF(2)^4.", &wide);
3288 assert!(
3289 !f2.faithful,
3290 "an element outside GF(2)^4 must fail: {:?}",
3291 f2.reasons
3292 );
3293 let f3 = claim_witness_faithful("A GF(2) Sidon set, at least 5 elements.", &wide);
3295 assert!(!f3.faithful, "{:?}", f3.reasons);
3296 }
3297
3298 #[test]
3303 fn faithful_binds_bh_order_and_constant_weight_params() {
3304 let bh = Witness::Bh {
3306 n: 3,
3307 h: 2,
3308 points: small_sidon(),
3309 claimed_size: None,
3310 };
3311 assert!(verify_witness(&bh).ok, "the B_2 witness is itself valid");
3312 let attack = claim_witness_faithful("a B_3 set in {0,1}^3: a(3) >= 4.", &bh);
3314 assert!(
3315 !attack.faithful,
3316 "B_3 claim cannot ride a B_2 witness: {:?}",
3317 attack.reasons
3318 );
3319 assert!(attack.reasons.iter().any(|r| r.contains("does not match")));
3320 let ok = claim_witness_faithful("a B_2 set in {0,1}^3: a(3) >= 4.", &bh);
3322 assert!(ok.faithful, "matched B_2 claim: {:?}", ok.reasons);
3323 let bare = claim_witness_faithful("a bh set in {0,1}^3: a(3) >= 4.", &bh);
3325 assert!(
3326 !bare.faithful,
3327 "unstated h routes to review: {:?}",
3328 bare.reasons
3329 );
3330
3331 let cw = Witness::ConstantWeight {
3333 n: 4,
3334 d: 2,
3335 w: 1,
3336 words: vec![vec![1, 0, 0, 0], vec![0, 1, 0, 0]],
3337 claimed_size: None,
3338 };
3339 assert!(
3340 verify_witness(&cw).ok,
3341 "the A(4,2,1) witness is itself valid"
3342 );
3343 let attack2 = claim_witness_faithful("constant weight code A(4,10,8) >= 2.", &cw);
3345 assert!(
3346 !attack2.faithful,
3347 "A(4,10,8) claim cannot ride an A(4,2,1) witness: {:?}",
3348 attack2.reasons
3349 );
3350 assert!(attack2.reasons.iter().any(|r| r.contains("does not match")));
3351 let ok2 = claim_witness_faithful("constant weight code A(4,2,1) >= 2.", &cw);
3353 assert!(ok2.faithful, "matched A(4,2,1) claim: {:?}", ok2.reasons);
3354 let bare2 = claim_witness_faithful("a constant weight code, a(4) >= 2.", &cw);
3356 assert!(
3357 !bare2.faithful,
3358 "unstated (d,w) routes to review: {:?}",
3359 bare2.reasons
3360 );
3361 }
3362
3363 #[test]
3366 fn canonical_claim_is_witness_derived() {
3367 let s = Witness::Sidon {
3368 n: 3,
3369 points: small_sidon(),
3370 claimed_size: None,
3371 };
3372 let c = canonical_claim(&s).expect("sidon has a canonical claim");
3373 assert!(c.contains("a(3) >= 4"), "{c}");
3374 let g = Witness::Gf2Sidon {
3376 elements: vec![1, 2, 4],
3377 claimed_size: None,
3378 };
3379 let cg = canonical_claim(&g).expect("gf2 has a canonical claim");
3380 assert!(cg.contains("a(3) >= 3"), "{cg}");
3381 assert!(
3383 canonical_claim(&Witness::Golomb {
3384 marks: vec![0, 1, 3]
3385 })
3386 .is_none()
3387 );
3388 }
3389
3390 #[test]
3392 fn faithful_golomb_routes_to_review() {
3393 let w = Witness::Golomb {
3394 marks: vec![0, 1, 3],
3395 };
3396 assert!(verify_witness(&w).ok);
3397 let f = claim_witness_faithful("Golomb ruler a(3) >= 3.", &w);
3398 assert!(
3399 !f.faithful,
3400 "golomb is not floor-admissible: {:?}",
3401 f.reasons
3402 );
3403 }
3404
3405 #[test]
3408 fn diff_triangle_accepts_valid_and_reports_scope() {
3409 let w = Witness::DiffTriangle {
3411 rows: vec![vec![0, 1, 3], vec![0, 4, 9]],
3412 claimed_scope: Some(9),
3413 };
3414 let r = verify_witness(&w);
3415 assert!(r.ok, "{}", r.message);
3416 assert!(r.message.contains("scope 9"));
3417 }
3418
3419 #[test]
3420 fn diff_triangle_rejects_global_difference_collision() {
3421 let w = Witness::DiffTriangle {
3423 rows: vec![vec![0, 1, 3], vec![0, 2, 5]],
3424 claimed_scope: None,
3425 };
3426 let r = verify_witness(&w);
3427 assert!(!r.ok);
3428 assert!(r.message.contains("repeats"));
3429 }
3430
3431 #[test]
3432 fn diff_triangle_rejects_non_increasing_and_nonzero_start() {
3433 assert!(!verify_diff_triangle(&[vec![0, 3, 1]], None).ok);
3434 assert!(!verify_diff_triangle(&[vec![1, 2, 4]], None).ok);
3435 }
3436
3437 #[test]
3438 fn diff_triangle_rejects_inflated_scope_claim() {
3439 let w = Witness::DiffTriangle {
3442 rows: vec![vec![0, 1, 3], vec![0, 4, 9]],
3443 claimed_scope: Some(100),
3444 };
3445 assert!(!verify_witness(&w).ok);
3446 }
3447
3448 #[test]
3449 fn gf2_sidon_accepts_distinct_xors_and_rejects_collision() {
3450 let ok = Witness::Gf2Sidon {
3452 elements: vec![0, 1, 2],
3453 claimed_size: Some(3),
3454 };
3455 assert!(verify_witness(&ok).ok);
3456 let bad = Witness::Gf2Sidon {
3458 elements: vec![0, 1, 2, 3],
3459 claimed_size: None,
3460 };
3461 assert!(!verify_witness(&bad).ok);
3462 let dup = Witness::Gf2Sidon {
3464 elements: vec![5, 5],
3465 claimed_size: None,
3466 };
3467 assert!(!verify_witness(&dup).ok);
3468 }
3469
3470 #[test]
3471 fn union_free_accepts_and_rejects_union_member() {
3472 let ok = Witness::UnionFree {
3474 n: 3,
3475 sets: vec![vec![1, 2], vec![1, 3], vec![2, 3]],
3476 claimed_size: Some(3),
3477 };
3478 assert!(verify_witness(&ok).ok);
3479 let bad = Witness::UnionFree {
3481 n: 2,
3482 sets: vec![vec![1], vec![2], vec![1, 2]],
3483 claimed_size: None,
3484 };
3485 assert!(!verify_witness(&bad).ok);
3486 }
3487
3488 #[test]
3489 fn rook_directions_counts_classes_and_checks_claim() {
3490 let ok = Witness::RookDirections {
3492 n: 2,
3493 perm: vec![1, 2],
3494 claimed_directions: Some(1),
3495 };
3496 assert!(verify_witness(&ok).ok);
3497 let bad = Witness::RookDirections {
3499 n: 2,
3500 perm: vec![1, 2],
3501 claimed_directions: Some(2),
3502 };
3503 assert!(!verify_witness(&bad).ok);
3504 let attack = Witness::RookDirections {
3506 n: 2,
3507 perm: vec![1, 1],
3508 claimed_directions: None,
3509 };
3510 assert!(!verify_witness(&attack).ok);
3511 }
3512
3513 #[test]
3514 fn unsat_cert_accepts_rup_proofs_and_rejects_corruption() {
3515 let w = Witness::UnsatCert {
3517 cnf: vec![vec![1], vec![-1]],
3518 proof: vec![LratStep {
3519 id: 3,
3520 literals: vec![],
3521 hints: vec![1, 2],
3522 rat_hints: vec![],
3523 }],
3524 };
3525 assert!(verify_witness(&w).ok);
3526 let w2 = Witness::UnsatCert {
3528 cnf: vec![vec![1], vec![2], vec![-1, -2]],
3529 proof: vec![LratStep {
3530 id: 4,
3531 literals: vec![],
3532 hints: vec![1, 2, 3],
3533 rat_hints: vec![],
3534 }],
3535 };
3536 assert!(verify_witness(&w2).ok);
3537 let bad = Witness::UnsatCert {
3539 cnf: vec![vec![1], vec![2], vec![-1, -2]],
3540 proof: vec![LratStep {
3541 id: 4,
3542 literals: vec![],
3543 hints: vec![1, 2],
3544 rat_hints: vec![],
3545 }],
3546 };
3547 assert!(!verify_witness(&bad).ok);
3548 let sat = Witness::UnsatCert {
3550 cnf: vec![vec![1, 2]],
3551 proof: vec![LratStep {
3552 id: 2,
3553 literals: vec![],
3554 hints: vec![1],
3555 rat_hints: vec![],
3556 }],
3557 };
3558 assert!(!verify_witness(&sat).ok);
3559 }
3560
3561 #[test]
3562 fn crt_partial_cover_accepts_real_rows_and_rejects_corruption() {
3563 let m = "8168305011630835886634520238999";
3564 let rows = vec![
3565 CrtCoverRow {
3566 p: 5,
3567 ord2: 4,
3568 ord3: 4,
3569 h: 4,
3570 t_p: 1,
3571 m_mod_p: 4,
3572 line: [1, 3, 0, 4],
3573 },
3574 CrtCoverRow {
3575 p: 7,
3576 ord2: 3,
3577 ord3: 6,
3578 h: 6,
3579 t_p: 1,
3580 m_mod_p: 6,
3581 line: [2, 1, 0, 6],
3582 },
3583 ];
3584 assert!(verify_crt_partial_cover(m, &rows).ok);
3585 let mut bad = rows.clone();
3587 bad[0].t_p = 2;
3588 assert!(!verify_crt_partial_cover(m, &bad).ok);
3589 let mut bad = rows.clone();
3591 bad[1].line = [2, 1, 1, 6];
3592 assert!(!verify_crt_partial_cover(m, &bad).ok);
3593 assert!(!verify_crt_partial_cover("9", &rows).ok);
3595 }
3596
3597 #[test]
3598 fn kummer_no_carry_accepts_erdos684_table_and_rejects_corruption() {
3599 let entries = vec![
3600 KummerEntry { k: 3, m: 36 },
3601 KummerEntry { k: 7, m: 88200 },
3602 KummerEntry { k: 12, m: 64033200 },
3603 ];
3604 assert!(verify_kummer_no_carry(&entries).ok);
3605 let bad = vec![KummerEntry { k: 3, m: 72 }];
3607 assert!(!verify_kummer_no_carry(&bad).ok);
3608 assert!(!verify_kummer_no_carry(&[KummerEntry { k: 25, m: 1 }]).ok);
3610 }
3611
3612 #[test]
3613 fn min_binom_gcd_accepts_erdos700_cases_and_rejects_corruption() {
3614 let cases = vec![
3615 MinGcdCase { n: 30, f: 6 },
3616 MinGcdCase { n: 77, f: 7 },
3617 MinGcdCase { n: 49, f: 7 },
3618 ];
3619 assert!(verify_min_binom_gcd(&cases).ok);
3620 assert!(!verify_min_binom_gcd(&[MinGcdCase { n: 30, f: 5 }]).ok);
3621 }
3622
3623 #[test]
3624 fn binom_deficiency_accepts_els93_row_and_rejects_corruption() {
3625 let good = DeficiencyEntry {
3627 k: 8,
3628 n: "44".to_string(),
3629 delta: 2,
3630 slots: Some(vec![4, 6]),
3631 };
3632 assert!(verify_binom_deficiency(&[good.clone()]).ok);
3633 let count_only = DeficiencyEntry {
3635 slots: None,
3636 ..good.clone()
3637 };
3638 assert!(verify_binom_deficiency(&[count_only]).ok);
3639 let bad = DeficiencyEntry {
3641 delta: 1,
3642 slots: None,
3643 ..good.clone()
3644 };
3645 assert!(!verify_binom_deficiency(&[bad]).ok);
3646 let bad = DeficiencyEntry {
3648 slots: Some(vec![4, 7]),
3649 ..good
3650 };
3651 assert!(!verify_binom_deficiency(&[bad]).ok);
3652 let big = DeficiencyEntry {
3654 k: 129,
3655 n: "3180883073384828665489".to_string(),
3656 delta: 1,
3657 slots: Some(vec![65]),
3658 };
3659 assert!(verify_binom_deficiency(&[big]).ok);
3660 }
3661
3662 #[test]
3663 fn binom_exception_enum_matches_els_for_small_k_and_rejects_corruption() {
3664 let els8: Vec<(u64, u64)> = vec![(7, 3), (13, 4), (14, 4), (23, 5), (62, 6), (44, 8)];
3666 assert!(verify_binom_exception_enum(8, &els8).ok);
3667 assert!(!verify_binom_exception_enum(8, &els8[1..]).ok);
3669 let mut padded = els8.clone();
3671 padded.push((100, 5));
3672 assert!(!verify_binom_exception_enum(8, &padded).ok);
3673 }
3674
3675 #[test]
3676 fn interval_product_accepts_erdos1056_example_and_rejects_corruption() {
3677 assert!(verify_interval_product(11, &[2, 4, 7]).ok);
3680 assert!(!verify_interval_product(12, &[2, 4, 7]).ok);
3682 assert!(!verify_interval_product(11, &[2, 4, 8]).ok);
3684 assert!(!verify_interval_product(11, &[4, 4, 7]).ok);
3686 }
3687
3688 #[test]
3689 fn sidon_accepts_valid_and_rejects_corrupted() {
3690 assert!(verify_sidon(&small_sidon(), 3).ok);
3691 let mut bad = small_sidon();
3694 bad.push(vec![1, 1, 0]);
3695 assert!(!verify_sidon(&bad, 3).ok, "corrupted Sidon must fail");
3696 }
3697
3698 #[test]
3699 fn packed_binary_sidon_path_matches_coordinate_semantics() {
3700 let good = small_sidon();
3701 let result = verify_sidon(&good, 3);
3702 assert!(result.ok, "{}", result.message);
3703 assert!(result.message.contains("10 pairwise sums"));
3704
3705 let collision = vec![vec![0, 0, 0], vec![1, 0, 0], vec![0, 1, 0], vec![1, 1, 0]];
3706 assert!(!verify_sidon(&collision, 3).ok);
3707 }
3708
3709 #[test]
3710 fn sidon_rejects_non_binary_and_dups() {
3711 assert!(!verify_sidon(&[vec![0, 2, 0]], 3).ok);
3712 assert!(!verify_sidon(&[vec![1, 0, 0], vec![1, 0, 0]], 3).ok);
3713 }
3714
3715 #[test]
3716 fn claimed_size_mismatch_fails() {
3717 let w = Witness::Sidon {
3718 n: 3,
3719 points: small_sidon(),
3720 claimed_size: Some(99),
3721 };
3722 let r = verify_witness(&w);
3723 assert!(!r.ok, "claimed_size 99 != actual 4 must fail");
3724 assert!(r.message.contains("claimed_size"));
3725 }
3726
3727 #[test]
3728 fn golomb_accepts_valid_and_rejects_corrupted() {
3729 assert!(verify_golomb(&[0, 1, 4, 6]).ok);
3731 assert!(!verify_golomb(&[0, 1, 2, 4]).ok);
3733 }
3734
3735 #[test]
3736 fn cap_accepts_valid_and_rejects_collinear() {
3737 assert!(verify_cap(&[vec![0], vec![1]], 1).ok);
3739 assert!(!verify_cap(&[vec![0], vec![1], vec![2]], 1).ok);
3741 }
3742
3743 #[test]
3744 fn bh_h2_matches_sidon() {
3745 assert!(verify_bh(&small_sidon(), 3, 2).ok);
3746 let mut bad = small_sidon();
3747 bad.push(vec![1, 1, 0]);
3748 assert!(!verify_bh(&bad, 3, 2).ok);
3749 }
3750
3751 #[test]
3752 fn covering_accepts_full_and_rejects_gap() {
3753 let full = vec![vec![0, 1, 2], vec![0, 1, 3], vec![0, 2, 3], vec![1, 2, 3]];
3755 assert!(verify_covering(&full, 4, 3, 2).ok);
3756 let gap = vec![vec![0, 1, 2], vec![0, 1, 3]];
3758 assert!(!verify_covering(&gap, 4, 3, 2).ok);
3759 }
3760
3761 #[test]
3762 fn constant_weight_checks_weight_and_distance() {
3763 let ok = vec![vec![1, 1, 0, 0], vec![0, 0, 1, 1]];
3765 assert!(verify_constant_weight(&ok, 4, 2, 2).ok);
3766 assert!(!verify_constant_weight(&[vec![1, 1, 1, 0]], 4, 2, 2).ok);
3768 }
3769
3770 #[test]
3771 fn costas_accepts_valid_and_rejects_nonpermutation() {
3772 assert!(verify_costas(&[0, 2, 3, 1]).ok);
3774 assert!(!verify_costas(&[0, 0, 1, 2]).ok);
3775 }
3776
3777 #[test]
3778 fn linear_code_verifies_distance_and_refuses_nonprime() {
3779 let g = vec![vec![1, 1, 1]];
3781 let r = verify_linear_code(&g, 2, 3);
3782 assert!(r.ok, "{}", r.message);
3783 assert!(!verify_linear_code(&g, 2, 4).ok);
3785 assert!(!verify_linear_code(&g, 4, 1).ok);
3787 }
3788
3789 #[test]
3790 fn witness_serde_round_trip() {
3791 let w = Witness::Sidon {
3792 n: 3,
3793 points: small_sidon(),
3794 claimed_size: Some(4),
3795 };
3796 let json = serde_json::to_string(&w).unwrap();
3797 assert!(json.contains("\"kind\":\"sidon\""));
3798 let back: Witness = serde_json::from_str(&json).unwrap();
3799 assert_eq!(back, w);
3800 assert!(verify_witness(&back).ok);
3801 }
3802}
3803
3804#[cfg(test)]
3805mod balanced_coloring_tests {
3806 use super::*;
3807 use std::collections::BTreeMap;
3808
3809 fn pentagon_k5() -> BTreeMap<String, u32> {
3810 let pent = [(0, 1), (1, 2), (2, 3), (3, 4), (0, 4)];
3811 let mut ec = BTreeMap::new();
3812 for i in 0..5usize {
3813 for j in (i + 1)..5 {
3814 let c = if pent.contains(&(i, j)) { 1 } else { 2 };
3815 ec.insert(format!("{i},{j}"), c);
3816 }
3817 }
3818 ec
3819 }
3820
3821 #[test]
3822 fn pentagon_coloring_is_balanced() {
3823 let r = verify_balanced_coloring(5, 2, &pentagon_k5());
3824 assert!(r.ok, "{}", r.message);
3825 }
3826
3827 #[test]
3828 fn flipped_edge_breaks_balance() {
3829 let mut ec = pentagon_k5();
3830 ec.insert("0,1".to_string(), 2);
3831 let r = verify_balanced_coloring(5, 2, &ec);
3832 assert!(!r.ok);
3833 }
3834
3835 #[test]
3836 fn dominates_orders_by_n_at_same_r() {
3837 let w5 = Witness::BalancedColoring {
3838 n: 5,
3839 r: 2,
3840 edge_colors: pentagon_k5(),
3841 };
3842 let w4 = Witness::BalancedColoring {
3843 n: 4,
3844 r: 2,
3845 edge_colors: BTreeMap::new(),
3846 };
3847 assert_eq!(dominates(&w5, &w4), Ok(true));
3848 assert_eq!(dominates(&w4, &w5), Ok(false));
3849 }
3850}
3851
3852#[cfg(test)]
3853mod rat_tests {
3854 use super::*;
3855
3856 fn rat_cert() -> (Vec<Vec<i64>>, Vec<LratStep>) {
3862 let cnf = vec![vec![1, 2], vec![-1, 3], vec![2], vec![-2]];
3863 let proof = vec![
3864 LratStep {
3865 id: 5,
3866 literals: vec![-1, -2],
3867 hints: vec![],
3868 rat_hints: vec![],
3869 },
3870 LratStep {
3871 id: 6,
3872 literals: vec![],
3873 hints: vec![3, 4],
3874 rat_hints: vec![],
3875 },
3876 ];
3877 (cnf, proof)
3878 }
3879
3880 #[test]
3881 fn blocked_clause_step_verifies_as_rat() {
3882 let (cnf, proof) = rat_cert();
3883 let r = verify_unsat_cert(&cnf, &proof);
3884 assert!(r.ok, "{}", r.message);
3885 }
3886
3887 #[test]
3888 fn rat_step_with_unhinted_resolvent_is_rejected() {
3889 let (mut cnf, proof) = rat_cert();
3894 cnf.push(vec![1, -3]);
3895 let r = verify_unsat_cert(&cnf, &proof);
3896 assert!(!r.ok);
3897 assert!(
3898 r.message.contains("neither RUP-implied nor RAT"),
3899 "{}",
3900 r.message
3901 );
3902 }
3903
3904 #[test]
3905 fn rat_with_supplied_resolvent_hints_verifies() {
3906 let (mut cnf, mut proof) = rat_cert();
3910 cnf.push(vec![1, -3]); proof[0].id = 6;
3912 proof[0].rat_hints = vec![(5, vec![4])];
3913 proof[1].id = 7;
3914 let r = verify_unsat_cert(&cnf, &proof);
3915 assert!(r.ok, "{}", r.message);
3916 }
3917
3918 #[test]
3919 fn unit_fraction_decomp_checks_exactness_coverage_and_ordering() {
3920 let c = |n, x, y, z| UnitFractionCase { n, x, y, z };
3921 let good = vec![c(3, 1, 4, 12), c(4, 2, 3, 6), c(5, 2, 4, 20)];
3923 assert!(verify_unit_fraction_decomp(5, &good).ok);
3924 assert!(!verify_unit_fraction_decomp(5, &[c(3, 1, 4, 12), c(5, 2, 4, 20)]).ok);
3926 assert!(!verify_unit_fraction_decomp(3, &[c(3, 1, 4, 13)]).ok);
3928 assert!(!verify_unit_fraction_decomp(4, &[c(3, 1, 4, 12), c(4, 2, 6, 6)]).ok);
3930 assert!(!verify_unit_fraction_decomp(3, &[c(3, 1, 4, 12), c(7, 2, 4, 28)]).ok);
3932 }
3933
3934 #[test]
3935 fn distinct_partial_sums_checks_validity_coverage_and_primality() {
3936 let full = vec![vec![1u64], vec![2], vec![1, 2]];
3939 assert!(verify_distinct_partial_sums(3, &full).ok);
3940 assert!(!verify_distinct_partial_sums(3, &[vec![1u64], vec![1, 2]]).ok);
3942 assert!(!verify_distinct_partial_sums(3, &[vec![1u64], vec![2], vec![1, 5]]).ok);
3948 assert!(!verify_distinct_partial_sums(4, &[vec![1u64]]).ok);
3950 }
3951
3952 #[test]
3953 fn powerful_triples_none_confirms_no_triple_and_counts_pairs() {
3954 let r = verify_powerful_triples_none(1000, None);
3956 assert!(r.ok, "{}", r.message);
3957 assert!(r.message.contains("pairs exist"));
3959 assert!(!verify_powerful_triples_none(1000, Some(0)).ok);
3961 assert!(verify_powerful_triples_none(10, None).ok);
3964 }
3965
3966 #[test]
3967 fn two_full_three_full_finds_the_complete_set() {
3968 assert!(verify_two_full_three_full(100, &[]).ok);
3971 assert!(!verify_two_full_three_full(100, &[8]).ok);
3973 assert!(verify_two_full_three_full(10, &[]).ok);
3976 }
3977
3978 fn brocard_witness(n: u64) -> u64 {
3981 fn is_prime(n: u64) -> bool {
3982 if n < 2 {
3983 return false;
3984 }
3985 let mut d = 2;
3986 while d * d <= n {
3987 if n.is_multiple_of(d) {
3988 return false;
3989 }
3990 d += 1;
3991 }
3992 true
3993 }
3994 fn modpow(mut b: u128, mut e: u128, m: u128) -> u128 {
3995 let mut r = 1u128;
3996 b %= m;
3997 while e > 0 {
3998 if e & 1 == 1 {
3999 r = r * b % m;
4000 }
4001 e >>= 1;
4002 b = b * b % m;
4003 }
4004 r
4005 }
4006 let mut p = n + 1;
4007 loop {
4008 if is_prime(p) {
4009 let pm = p as u128;
4010 let mut f = 1u128;
4011 for k in 1..=n {
4012 f = f * (k as u128) % pm;
4013 }
4014 let r = (f + 1) % pm;
4015 if r != 0 && modpow(r, (pm - 1) / 2, pm) == pm - 1 {
4016 return p;
4017 }
4018 }
4019 p += 1;
4020 }
4021 }
4022
4023 #[test]
4024 fn brocard_no_square_certifies_a_range_and_rejects_tampering() {
4025 let (n_min, n_max) = (8u64, 40u64);
4027 let cases: Vec<BrocardCase> = (n_min..=n_max)
4028 .map(|n| BrocardCase {
4029 n,
4030 p: brocard_witness(n),
4031 })
4032 .collect();
4033 let w = Witness::BrocardNoSquare {
4034 n_min,
4035 n_max,
4036 cases: cases.clone(),
4037 };
4038 let r = verify_witness(&w);
4039 assert!(r.ok, "should certify [{n_min},{n_max}]: {}", r.message);
4040
4041 let known = Witness::BrocardNoSquare {
4043 n_min: 4,
4044 n_max: 7,
4045 cases: vec![
4046 BrocardCase { n: 4, p: 0 },
4047 BrocardCase { n: 5, p: 0 },
4048 BrocardCase {
4049 n: 6,
4050 p: brocard_witness(6),
4051 },
4052 BrocardCase { n: 7, p: 0 },
4053 ],
4054 };
4055 assert!(
4056 verify_witness(&known).ok,
4057 "4,5,7 are the known squares; 6 is not"
4058 );
4059
4060 let mut bad = cases.clone();
4062 bad[0].p = bad[0].n * (bad[0].n + 1); assert!(
4064 !verify_witness(&Witness::BrocardNoSquare {
4065 n_min,
4066 n_max,
4067 cases: bad,
4068 })
4069 .ok,
4070 "a non-prime witness must fail"
4071 );
4072 let short: Vec<BrocardCase> = cases[1..].to_vec();
4074 assert!(
4075 !verify_witness(&Witness::BrocardNoSquare {
4076 n_min,
4077 n_max,
4078 cases: short,
4079 })
4080 .ok,
4081 "incomplete coverage must fail"
4082 );
4083 assert!(
4085 !verify_witness(&Witness::BrocardNoSquare {
4086 n_min: 8,
4087 n_max: 8,
4088 cases: vec![BrocardCase { n: 8, p: 0 }],
4089 })
4090 .ok,
4091 "n=8 with no witnessing prime must fail (8 is not a known square and p=0 invalid)"
4092 );
4093 }
4094
4095 #[test]
4096 fn semiprime_egyptian_checks_decompositions_and_rejections() {
4097 let good = Witness::SemiprimeEgyptian {
4100 cases: vec![
4101 SemiprimeEgyptianCase {
4102 a: 1,
4103 b: 6,
4104 denominators: vec![6],
4105 },
4106 SemiprimeEgyptianCase {
4107 a: 4,
4108 b: 15,
4109 denominators: vec![6, 10],
4110 },
4111 SemiprimeEgyptianCase {
4112 a: 7,
4113 b: 30,
4114 denominators: vec![6, 15],
4115 },
4116 SemiprimeEgyptianCase {
4117 a: 1,
4118 b: 3,
4119 denominators: vec![6, 10, 15],
4120 },
4121 ],
4122 };
4123 let r = verify_witness(&good);
4124 assert!(r.ok, "valid semiprime-Egyptian cases: {}", r.message);
4125
4126 assert!(
4128 !verify_semiprime_egyptian(&[SemiprimeEgyptianCase {
4129 a: 1,
4130 b: 12,
4131 denominators: vec![12],
4132 }])
4133 .ok,
4134 "12 is not a squarefree semiprime"
4135 );
4136 assert!(
4138 !verify_semiprime_egyptian(&[SemiprimeEgyptianCase {
4139 a: 1,
4140 b: 30,
4141 denominators: vec![30],
4142 }])
4143 .ok,
4144 "30 has three prime factors"
4145 );
4146 assert!(
4148 !verify_semiprime_egyptian(&[SemiprimeEgyptianCase {
4149 a: 1,
4150 b: 5,
4151 denominators: vec![6],
4152 }])
4153 .ok,
4154 "1/6 != 1/5"
4155 );
4156 assert!(
4158 !verify_semiprime_egyptian(&[SemiprimeEgyptianCase {
4159 a: 4,
4160 b: 15,
4161 denominators: vec![10, 6],
4162 }])
4163 .ok,
4164 "denominators must be strictly increasing"
4165 );
4166 assert!(
4168 !verify_semiprime_egyptian(&[SemiprimeEgyptianCase {
4169 a: 1,
4170 b: 12,
4171 denominators: vec![14, 21],
4172 }])
4173 .ok,
4174 "b=12 is not squarefree"
4175 );
4176 }
4177}