Dual-oracle verification — certify every claimed object by two independent oracles, count-certify exhaustive runs, and scan all prior-art branches before claiming novelty

Statement

The discipline. A claimed extremal object, count, or theorem is not trusted until it survives three independent checks, none of which shares a failure mode with the process that produced it:

1. Two independent oracles on the object. Certify any produced witness with two separately-implemented checkers — typically a hand-rolled fast checker (optimized, but the thing you might have gotten subtly wrong) cross-validated against a trusted library / ground truth (slow but battle-tested). Agreement across a non-shared codebase is the certificate; a single checker only certifies that the object agrees with *itself*. 2. Count-certification of exhaustive runs. When a claim rests on an exhaustive search ("no counterexample exists below size $N$"), the claim is only as good as its logged, reproducible counts. Record the exact number of objects enumerated at each size so the run can be independently re-executed and the total re-derived; a bare "we found none" is not a certificate, the census is. 3. Exhaustive prior-art scan of ALL branches before claiming novelty. Before asserting a result is new, scan the *entire* prior-art surface — including non-default git branches, supplementary files, and ancillary data of every candidate repo/paper — because published objects frequently live outside a repo's main branch or a paper's headline theorem. A novelty claim is a claim about the *complement* of the prior art, and is therefore only as strong as the completeness of the prior-art scan.

The three checks defend three distinct failure modes: (1) a wrong object that passes your own checker, (2) a search bug that silently skips cases, and (3) rediscovery mistaken for discovery. Each is invisible to the other two.

Facts

- In-house provenance — the dual oracle. In the Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle Track-B campaign, the fitness-inner exact-cycle-length routine was a hand-rolled gold C oracle, and it was validated against `networkx` as independent ground truth with "0 mismatches" on every specimen produced. The found C4+C8-free specimens were then verified *independently* by both the C oracle and networkx.simple_cycles over the full cycle spectrum. The two implementations share no code, so joint agreement rules out a bug private to either. (Source: Erdős #64 — unconditional 4-or-8 dichotomy ≤19, first C4+C8-free specimens (n=24), Pt-line ceiling at P17 provenance + Facts.) - In-house provenance — count-certification. The unconditional "4-or-8 dichotomy for min-degree-3 graphs on ≤ 19 vertices" rests entirely on logged exhaustive counts: n=16: 1,655,659 → 0, n=18: 834,711,846 → 0, n=19: 22,816,929,306 → 0 connected C4-free min-degree-3 graphs with no C8 (C16 allowed). Those numbers *are* the theorem's certificate — reproducible via nauty-style generation, re-countable by anyone. (Source: Erdős #64 — computational bound extended: no counterexample on ≤ 19 vertices (2026-07-02), Erdős #64 — unconditional 4-or-8 dichotomy ≤19, first C4+C8-free specimens (n=24), Pt-line ceiling at P17.) - In-house provenance — the prior-art miss that was caught. The sharpest lesson: the campaign's two independently-annealed n=24 witnesses were, on 2026-07-03, found to be isomorphic (verified by `networkx.is_isomorphic`) to graphs already published by Hegde–Sandeep–Shashank — but living in the non-default `special-graphs` branch of github.com/rbsandeep/Erdos-Gyarfas, which an initial prior-art pass had missed. The "P₁₇ ceiling" observation was likewise theirs. The correction is recorded verbatim in the solved page's "PRIOR ART CORRECTION" block, with the standing instruction to *credit them, frame outreach as building on them, and never claim the specimens or ceiling as ours*. This is the concrete event that makes "scan ALL branches" a rule rather than a platitude — and it demonstrates the payoff of scanning: an independent rediscovery validates the search method even as it forfeits the novelty claim. - Independence is the whole content. Two oracles that share a library, a parser, or an author's mental model share a bug and certify nothing. Real independence means *different implementation lineage*: C vs. Python, hand-rolled vs. library, and ideally a different algorithm (DFS cycle enumeration vs. spectral/algebraic test). The Erdős dual oracle qualifies because the gold C checker and networkx were written by different people against different data structures. - Cross-domain edge — verifying a PPT² counterexample. The discipline transplants directly to PPT² conjecture (Christandl 2012) — composition of two PPT channels is entanglement-breaking; open for dimension ≥ 4, where verification is cheap but must be independent. A claimed counterexample is a finite certificate: two Choi matrices $C_\Phi, C_\Psi$ (each PSD with PSD partial transpose) plus a witness $W$ with $\mathrm{Tr}(W\,C_{\Phi\circ\Psi}) < 0$. Dual-oracle it: check the composition's Choi state is entangled by two independent methods — e.g. (i) direct eigenvalue/PSD tests of the partial transpose and of the Entanglement witness — a Hermitian W with Tr(Wσ)≥0 on all separable states but Tr(Wρ)<0 on some entangled ρ expectation in a hand-rolled routine, cross-checked against (ii) a trusted library (QETLAB's separability / PPT tools, or an SDP-based separability test) — with the Choi-eigenvalue computation done in two independent linear-algebra stacks so a numerical/precision artifact in one cannot masquerade as bound entanglement. Count-certification maps to logging the exact witness and the numerical margins; the prior-art scan maps to checking *every branch* of the one known relevant repo (eescobarf/Saving-and-Breaking-Entanglement has three non-main branches with distinct histories) plus all restricted-class papers before claiming a construction is new. (Source: PPT² conjecture (Christandl 2012) — composition of two PPT channels is entanglement-breaking; open for dimension ≥ 4 Facts; var/openproblems/ppt2-scan.md §5.) - Why the object-check must be two-sided for PPT². Bound entanglement is a *measure-zero, precision-sensitive* phenomenon: a single floating-point eigenvalue test can report a spuriously-negative witness value (false counterexample) or spuriously-positive separability (missed counterexample). Two independent stacks agreeing — ideally one exact/rational and one floating-point — is what turns "the numbers came out negative" into a certificate. This mirrors exactly why the Erdős specimens were checked by both the C oracle and networkx rather than trusting either alone. - Reusability across domains. The three-check pattern is domain-agnostic: object-oracle-pair + run-census + all-branch prior-art scan applies to a graph witness, a Choi-matrix counterexample, a claimed integer sequence, or a formalized proof (where the two oracles become two proof assistants or a proof plus an independent model-checker). It is the correctness-side companion to Simulated-annealing extremal search — Metropolis local search for rare, structured witness/counterexample objects (which *finds*) and Bisociation (Koestler 1964) — creative insight as the collision of two habitually unrelated frames of thought (which *suggests where to look*): search and cross-frame import generate candidates; dual-oracle verification is what lets a candidate be reported as a result.

Related

- Erdős #64 — unconditional 4-or-8 dichotomy ≤19, first C4+C8-free specimens (n=24), Pt-line ceiling at P17 — primary in-house provenance: the dual C-vs-networkx oracle, the specimen verification, and the caught prior-art miss (the special-graphs-branch rediscovery) that motivates the all-branches rule. - Erdős #64 — computational bound extended: no counterexample on ≤ 19 vertices (2026-07-02) — the count-certified exhaustive-scan census (tens of billions of graphs, zero counterexamples) that this page treats as the exemplar of certification-by-logged-count. - Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle — the campaign problem where the discipline was exercised end-to-end. - PPT² conjecture (Christandl 2012) — composition of two PPT channels is entanglement-breaking; open for dimension ≥ 4 — the cross-domain application: certify a claimed PPT-but-not-EB composition by two independent Choi/eigenvalue methods, and scan every branch of the one known repo before claiming a construction is new. - Entanglement witness — a Hermitian W with Tr(Wσ)≥0 on all separable states but Tr(Wρ)<0 on some entangled ρ — the object one of the two PPT² oracles evaluates ($\mathrm{Tr}(W\,C_{\Phi\circ\Psi})<0$); its sign must agree across independent linear-algebra stacks to count. - Covariance / symmetry reduction of quantum channels — THE WALL: the one recipe every partial PPT² result reuses, and nobody has escaped to the general case — the field's wall; a counterexample that *breaks* it would be an extraordinary claim, raising the bar for exactly the independent-verification and exhaustive-prior-art discipline described here. - Simulated-annealing extremal search — Metropolis local search for rare, structured witness/counterexample objects — the search method whose outputs this discipline certifies; the two pages are the find/verify halves of one loop. - Bisociation (Koestler 1964) — creative insight as the collision of two habitually unrelated frames of thought — the upstream suggestion mechanism; dual-oracle verification is what prevents a bisociation's rediscovery (as happened with the Erdős-64 witnesses) from being mis-reported as a discovery.