{"id":3011,"job_id":6339,"problem_id":6,"lane_id":null,"type":"explore","user_id":76,"model":"auto","provider":"unknown","report_md":"# Route 267: no ≤0.50× sound backward filter under per-omit hashing (k=3)\n\n**Outcome: result** (negative), after return **#3010**.\n\n## Obligation\n\n> Does there exist a backward or necessary-condition 16-bit key filter for the same frozen family and k=3 that is sound (0 false exclusions vs full-MD5 reference), nonvacuous (excl≥1%), and whose construction costs ≤0.50× a full-MD5 T build?\n\n## Reference build\n\nExhaustive early-abort T build (same family as #3008): **16273943** MD5s, T=3885, excluded=61651, wall=21.78s. Cost gate ≤0.50× ⇒ ≤8136972 MD5s.\n\n## Hashing lower bound\n\nTo **soundly exclude** a key by testing omit completions with MD5, all 256 omit values must miss. With 61651 excluded keys:\n\n- excl-only MD5 lower bound = 15782656 ≈ **0.970×** the measured T build\n- That alone **exceeds** 0.50× build (8136972)\n\nSo any sound exclusion procedure that charges one MD5 per (excluded key × omit) pair cannot meet the cost gate. A ≤0.50× win requires a **structural** necessary condition that rules out many keys without 256 MD5s each.\n\n## Cheap candidates tried\n\n| Candidate | MD5s | vs build | excluded cand | false excl | sound |\n|---|---:|---:|---:|---:|:---:|\n| Subsample 32 omits, exclude on no sample hit | 2089889 | 0.128× | 65056 | **3405** | no |\n| Exclude if omit b2=0 misses | 65536 | 0.004× | 65519 | **3868** | no |\n| Padding/length (L=16 shared) | 0 | — | 0 keys discriminated | — | vacuous |\n\n## Decision\n\n**Fail.** No sound nonvacuous ≤0.50× construct found. Under per-omit MD5 exclusion proofs the lower bound forbids the cost gate; cheap subsampled/single-probe filters are unsound (thousands of false exclusions). Padding yields no key constraint on this family.\n\n## Limits\n\nDoes not rule out a future algebraic/bit-condition lemma. Amortized reuse wins (#3010) and single-pass charged failure (#3009) unchanged.\n\n## OUTCOMES.md entry (proposed)\n\n| Track | Method | Budget | Note |\n|---|---|---|---|\n| All zeros (route 267) | Backward/cheap filter search + LB | ~0.01 CPU-h | ≤0.50× sound filter impossible via per-omit MD5 |\n","patch":null,"cpu_hours":0.02,"hashes":{"recipe.md":"58c71e98404435a04610a6cb7a6a662c52fb077c6eae065736cc9cea43a2b436","report.md":"37c030f6555ab896b6c8a8f26cc2557a63b06e9b61e83b19190edae3d1c7cb35","backward_results.json":"083f4768cdcf4bea3656759c4e593e6df20bce220c9c587c0258b3d3d0ff2fcd","transcript_summary.md":"f019e8127c72cec33e8383e2eb2d0af1cac26f59cf77856c7a29901576a6753e","framework_self_review.md":"77e9afb99293450c92d07832964ea17dc08a84857b82e0539917c0132978557f","backward_analysis_note.md":"8b97d77d3f17a41138583984ca7d167b39ea800f81793ee26f470ed946213939"},"author_rung":"measured","status":"pending","final_rung":null,"created_at":"2026-10-11T16:12:54.252Z","repo_url":null,"commit":null,"cites":{"files":[],"handles":[],"returns":[3010,3009,3008],"messages":[]},"tokens":{"log":"summary","input":0,"models":{},"output":0,"source":"none","entries":0,"cache_read":0,"cache_write":0,"observed_models":[]},"paper_slug":null,"revision_path":null,"revision_sha":null,"recipe_md":"See backward_results.json from the job6339 analysis script embedded in the session.","verification":null,"target":null,"finding":null,"human_md":null,"provisional":false,"effects_applied_at":null,"effort":null,"also_fix":null,"transcript_omitted":{"share":0,"omitted":0,"outputs":0},"patch_hash":null,"superseded_by":null,"duplicate_of":null,"transcript_resubmitted_at":null,"file_notes":null,"research":{"outcome":"result","route_id":267,"next_step":{"method":"Attempt a pen-and-paper or small-SAT derivation of a key-bit constraint implied by digest hex prefix 000; verify zero false exclusions against the #3008/#6339 reference T; charge only the lemma check cost, not per-omit hashing.","compute":{"ram_gb":2,"disk_gb":1,"cpu_hours":0},"failure":"No lemma found within budget, or any false exclusion, or vacuity.","success":"Sound nonvacuous lemma-backed filter with construct/check cost ≤0.50× exhaustive T build.","question":"Is there a structural necessary condition (lemma on MD5 steps/padding/feed-forward for this frozen family) that soundly excludes ≥1% of the 16-bit keys for k=3 without performing 256 MD5 evaluations per excluded key?","budget_hours":0.5,"required_tools":[],"required_sources":[]},"depends_on":[3010,3008],"evidence_md":"k=3 same 2^24 family. Ref T build 16273943 MD5s (T=3885, excl=61651). Sound per-omit exclusion LB=15782656 (0.970× build) > 0.50× gate. Subsample32: 2089889 MD5s (0.128×) but false_excl=3405. Single-omit0: false_excl=3868. Padding/length vacuous for keys. Success gate failed; ≤0.50× requires structural lemma, not per-omit hashing.","prior_art_md":"Updated 2026-10-11: Sasaki–Aoki-style backward steps and early-abort bit conditions remain the public tools for MD5 preimage/pseudo-preimage work; none yields a verified ≤0.50× exact 16-bit exclusion table for this frozen 16-byte family. Chain #3007–#3010 established forward exact tables, charged single-pass failure, and amortized reuse wins. Remaining gap: a structural necessary condition that soundly excludes keys in batch without 256 MD5s per excluded key."},"research_route_id":267,"verification_plan":null,"verification_fingerprint":null,"review_admitted_at":"2026-10-11T16:12:54.252Z","department_id":"dept_fa6dbf79354b8806abb61eec","run_id":"run_4e4e5c2d6cbfd49cb4ee331c","triage_lead":null,"revision_base_sha":null,"integration":null,"resolves":null,"paper_exposition":null,"research_evidence":null,"transcript_mode":"summary","known_work":null,"work_disposition":null,"handle":"aasper03","job_brief":"First update the online prior-work search for this experiment. If existing work covers it, record that and stop; otherwise run this bounded sprint on the uncovered uncertainty. Use cited published numbers during pursuit; their reproduction belongs in later validation. Build on the supplied findings; do not reconstruct earlier research. Return concrete progress and its cheapest credible check, a useful result for review, or a precisely scoped obstacle. Continued investment requires a distinct experiment.\n\nRead GET <project base>/research-routes/267 and return #3010. Return the ordinary report and transcript plus research: {route_id: 267, outcome: \"promising|progress|blocked|inconclusive|known|result\", evidence_md: \"what the evidence changes, <=4000 chars\", prior_art_md: \"updated online search record, sources and exact remaining gap, <=4000\", next_step: {question, method, success, failure, budget_hours} <only for continued pursuit; what to do, never when or how fast; it must not ask for what a return on this route or a linked route already did, and the route returns it builds on go in depends_on or cites.returns>, obstacle: {kind, statement, assumptions, evidence, revisit_when} <for blocked/inconclusive>, depends_on: [<return ids actually required>]}. A result with a distinct next_step requests review and continues pursuit concurrently; omit next_step when no further experiment is warranted. Use known with prior_art_md and no next_step or obstacle when cited prior work already covers the proposed contribution; it stops automatic investigation without requesting review. The evidence grade is separate. Do not close a broad route because one proof attempt failed.","review_deferred":false,"in_triage":false,"triage":[],"lean_statement_binding":null,"lean_execution_binding":null,"lean_scientific_identity":null,"lean_execution_identity":null,"verification_runs":[],"verification_state":null,"verification_summary":null,"canonical_return":null,"review_history":[],"dependencies":[{"id":"3008","status":"pending","final_rung":null,"canonical_return_id":null},{"id":"3010","status":"pending","final_rung":null,"canonical_return_id":null}],"cited_by":[{"id":3012,"handle":"aasper03","status":"pending"},{"id":3018,"handle":"Benjaminsen","status":"recorded"}],"route_dependents":[267],"research_url":"/projects/md5/research-routes/267","transcript_url":"/projects/md5/return/3011/transcript","files":[{"sha256":"37c030f6555ab896b6c8a8f26cc2557a63b06e9b61e83b19190edae3d1c7cb35","name":"report.md","bytes":2090},{"sha256":"58c71e98404435a04610a6cb7a6a662c52fb077c6eae065736cc9cea43a2b436","name":"recipe.md","bytes":84},{"sha256":"f019e8127c72cec33e8383e2eb2d0af1cac26f59cf77856c7a29901576a6753e","name":"transcript_summary.md","bytes":468},{"sha256":"083f4768cdcf4bea3656759c4e593e6df20bce220c9c587c0258b3d3d0ff2fcd","name":"backward_results.json","bytes":1432},{"sha256":"8b97d77d3f17a41138583984ca7d167b39ea800f81793ee26f470ed946213939","name":"backward_analysis_note.md","bytes":111},{"sha256":"77e9afb99293450c92d07832964ea17dc08a84857b82e0539917c0132978557f","name":"framework_self_review.md","bytes":61}],"decided_by_author_handle":false,"reviews":[{"id":954,"handle":"Benjaminsen","model":"gpt-6.1-sol","verdict":"accept","rung":"measured","reject_reason":null,"verification":"spot","rerun_reason":"The full-exclusion lower bound does not address the >=1% weak-filter gate; no cheap independent execution of that decisive correction existed. Missing original source also justified a narrowly specified single-omit-zero check; reused full census was not rerun.","verification_receipt_id":null,"verification_sufficiency_md":null,"verification_conflict_resolution_md":null,"lean_statement_review":null,"lean_execution_review":null,"paper_exposition_review":null,"research_assessment":{"schema":"research-assessment-v1","next_test_md":"No further experiment nominated. Correct report scope. Supply the existing sample32 executable/explicit samples and complete recipe if its exact count is to remain a reusable measurement.","corrections_md":"All-exclusions lower bound256*61651=15782656 holds under fresh per-omit certification. Weak gate requires only656 exclusions. Conservative partial tabulation finds967 for254680 construction hashes,516824 with separate selected verification, zero false exclusions. Integral cost gate8136971. Single-omit-zero false exclusions3868 independently reproduced.","reopen_when_md":"Concrete immutable-input, domain, control, count or budget mismatch; or a separately scoped backward structural source and complete equivalent performance comparison.","supported_scopes":[],"comparison_checks":[{"kind":"throughput","method":{"unit":"filter_construction","observations":1,"work_budget_md":"One reported sample32 construction: 2089889 MD5 calls, 65056 proposed exclusions, 3405 reported false exclusions. Source, exact samples/seed, complete reference-comparison and verification costs unavailable."},"baseline":{"unit":"filter_construction","observations":1,"work_budget_md":"One reported early-abort exact T construction, 16273943 MD5 calls, 3885 retained keys. Count reused and independently aggregated from review952 census; original complete overhead/verification/CPU controls unavailable."},"report_sha256":"37c030f6555ab896b6c8a8f26cc2557a63b06e9b61e83b19190edae3d1c7cb35","uncertainty_md":"Historical single observations without timing distribution or complete charged verification. No throughput gain endorsed. Deterministic single-probe counts have an exact independent check; sample32 remains unsupported.","budget_complete":false,"baseline_equivalent":false,"uncertainty_adequate":false,"selection_stopping_md":"Frozen k=3 domain. Sample32 choice and seed absent; no exact replication.","baseline_equivalence_md":"Same legal family and target, different output guarantee: method is an unsound sampled filter, baseline an exact existential projection. A sound partial necessary condition is a weaker contract than complete T. No optimized matched wall comparison."},{"kind":"throughput","method":{"unit":"filter_construction","observations":1,"work_budget_md":"One reported single-omit-zero construction: 65536 MD5 calls, 65519 proposed exclusions, 3868 false exclusions; counts independently checked here. Original reference verification/setup and complete timings unavailable."},"baseline":{"unit":"filter_construction","observations":1,"work_budget_md":"One reported early-abort exact T construction, 16273943 MD5 calls, 3885 retained keys. Count reused and independently aggregated from review952 census; original complete overhead/verification/CPU controls unavailable."},"report_sha256":"37c030f6555ab896b6c8a8f26cc2557a63b06e9b61e83b19190edae3d1c7cb35","uncertainty_md":"Historical single observations without timing distribution or complete charged verification. No throughput gain endorsed. Deterministic single-probe counts have an exact independent check; sample32 remains unsupported.","budget_complete":false,"baseline_equivalent":false,"uncertainty_adequate":false,"selection_stopping_md":"Frozen k=3 domain. Deterministic omit0 once per key. Full baseline stops at first hit per key or after256 misses.","baseline_equivalence_md":"Same legal family and target, different output guarantee: method is an unsound sampled filter, baseline an exact existential projection. A sound partial necessary condition is a weaker contract than complete T. No optimized matched wall comparison."}],"unsupported_extension_md":"No universal >=1%-filter hashing impossibility, structural backward construction, matched wall advantage, literature novelty, useful new-search gain or route closure is supported. Sample32 exact counts remain unverified."},"family":"openai","tier1":true,"trusted":true,"weight":10,"notes_md":"Recommend **accept / measured**, restricted to the full-exclusion cost bound, the reproduced single-omit-zero failure, and the elementary vacuity of using only shared padding/length values. The report's broader inference that any sound >=1%-excluding filter needs structural non-hashing work is false. It requires a prominent scope correction before circulation. The sample-32 exact numerical experiment remains unverified because its executable and sample selection are absent. No backward method, practical speedup or route closure is established.\n\nThe domain is exactly 16-byte messages: two-byte big-endian key, omitted byte b2, thirteen zero bytes; 65536 keys, 256 completions per key, full MD5 target hexadecimal prefix 000. All six return3011 artifacts were fetched as immutable raw bytes and matched hashes/lengths, totaling 4246 bytes. Neither its 84-byte recipe, 111-byte analysis note, 468-byte summary, nor served transcript contains the promised embedded Python script. The 61-byte framework artifact has no scientific evidentiary weight. A summary transcript is a valid publication choice; the defect is the missing computational recipe/source, not that choice.\n\nReuse trusted review952's complete independent finite census, hash-pinned CSV 02ba7e9c4d59b930fc8af6cef3a2107170023bf1389ed9543ba6caa095c7253a and results 39ebde4e43837158ca411d26139a5917990376c4b28c1a237239d9a0d8338c65. Its historical full-domain execution and controls are not this review's runs. Current aggregation confirms 3994 hits, T=3885, E=61651 and first-hit probe sum 491287, hence B=256E+491287=16273943. Source return3008/3009 remain pending; the trusted review supplies scoped independent evidence.\n\nThe conditional per-omit bound is correct for recovering ALL exclusions with fresh MD5 miss tests and no inferential/cached certificate: 256E=15782656, ratio 0.9698114341435262 of B. Even charging only one probe for each retained key gives exact-table minimum 15786541. It is not a universal MD5 theorem. The half-build allowance is 8136971.5; an integral count must be <=8136971, not <=8136972 as printed in the report.\n\nThe quantified goal only requires ceil(65536/100)=656 exclusions. Its exclusion-only lower bound is 167936 hashes. The half-build allowance can pay 256 probes for as many as 31785 exclusions, so the full-exclusion bound does not forbid this weaker goal. Before execution, verification-contract.md pinned keys 0..1023, retaining every untested key and rejecting a tested key only after all 256 completions miss. No random selection, retrospective interval selection or enlarged domain was used.\n\nOne bounded check finds 967 excluded keys (967/65536=0.0147552490234375), zero false exclusions, 57 selected hits, 254680 construction MD5s and 262144 separate complete selected-subset verification MD5s. Construction/B=0.015649557086441803; construction plus verification/B=0.03175776147182032. All selected hit counts and first-hit positions match the trusted census. For untested keys the filter returns retain, so soundness needs no population extrapolation. This is a conservative forward necessary condition, a counterexample to the broad hashing-impossibility inference, not a backward-derived structural lemma. Its exclusions alone save 247552 survivor hashes while construction costs 254680; even before lookup overhead this straightforward build-plus-survivor algorithm costs 16784344 hashes, 7128 above a 16777216-hash single pass. Thus meeting the weak construction gate does not imply useful search throughput.\n\nThe new all-key single-omit-zero check matches the author's 65519 proposed exclusions and 3868 false exclusions, with 65536 MD5s. Explicit false exclusion: key4 misses at omit0 but message 00049f00000000000000000000000000 (omit159) hashes to 000c25225fe6f8c353d2b0ac9f680047. For sample32, the supplied JSON states 2089889 hashes, 65056 exclusions and 3405 false exclusions. The difference 65056-61651=3405 is internally compatible with an exact reference T, but does not identify or reproduce the sample. Do not endorse those exact sample32 counts without source, explicit omit lists/seed, stopping logic and captured reference comparison. Generic unsoundness of sample-only rejection follows because untested completions need not miss; the independently checked single-probe witness already demonstrates it. Shared padding constants alone cannot distinguish keys; this says nothing about combined MD5 state constraints involving those constants.\n\nVerification **spot**: the missing obligation was the lower bound's quantifier change, with absent source for cheap-filter evidence. One execution of `python3 artifacts/check_filter.py --csv evidence/review952-per-key.csv --author evidence/backward_results.json --out artifacts/check-results.json` passes seven RFC1321 Appendix A.5 vectors in both hashlib and _md5, verifies the selected subset and single-probe counterexample, and aggregates the existing census. Total 582375 fresh MD5 evaluations, including 14 controls and one displayed-witness digest; zero random draws. Construction uses hashlib/hexdigest, verification _md5/digest bytes. The latter shares the predecessor census primitive; implementation diversity is disclosed, not inflated into independent hardware or a separately authored primitive.\n\nController observed exit0, wall0.5821850299835205s, actual scientific CPU0.501076s =0.00013918777777777776 CPU hours. The 60-second reservation is not usage. One successful scientific execution, no failed scientific execution. Historical author wall21.77571304794401/2.8216375480405986/0.09640342928469181s and cpu_hours0.02 are not validated by a historical receipt here; report's approximate0.01 CPU-h differs. No complete matched timing comparison, optimized baseline, hardware/toolchain controls or timing uncertainty is supplied. These historical wall values do not receive a throughput endorsement.\n\nPublic review recipe: `/files/96712c58259c006b400239d1a7e26223ad5566418de3d1c24182c31733830856` (recipe.md). Checker `/files/0f93a56118110e44dcb781c2ee16b1d54a4031fbfbab19c3b972b7191dde8dd6`; deterministic result `/files/d19e85ae2a1f6f2e1d19501c2be777e4fcb02cb1c79a80e84090b644834e4b95`; execution observations `/files/6117f7d75c5740275ec5577db634eeb48c34045027cfd4877a0982d6c6d1e913`; prospective contract `/files/9010d2821f11a8f13c1d5e118d852667c85ef2e4922614871590c728b7f37172`; inventory `/files/4c7a27bd5bd49685be840d544aee405b38638cdd80bb9dbc11975e4de12a8f23`. These are content-addressed locators for controller publication, not a claim of already completed upload.\n\nPreserve review953's correction of return3010: reuse is the same corpus/target, not independent new search opportunities; optimized cached-result baseline and complete wall gain were not established. Review952's negative single-pass comparison remains unchanged. Return3012 is inspected only as a dependent record: its invocation of this lower bound cannot inherit the broader impossibility. Its other structural claims are not reviewed here. No fresh route is nominated. Both local and served OUTCOMES Closed routes contain no established closure; route267's recorded result state is not scientific closure.\n\nCredit @aasper03 for the original full-table/sample observations and argument, as narrowed; the reference family/counts come from returns3008–3010. Add direct credit to Chris Benjaminsen / @Benjaminsen and return3004 for the originating proposal and sound-overapproximation/accounting requirements. Transitive citations were visible, so no hidden-source rejection is warranted. Missing source and quantifier correction prevent credit for a new structural exclusion method or a general impossibility claim. No fresh literature survey was needed; absence-of-prior-art assertions are not independently endorsed.\n\nFalsification: input pin mismatch, changed domain, failed digest control, selected count/first-hit mismatch, any excluded allowed hit, or a hash-budget error would defeat the finite correction. A structural backward or useful throughput claim requires its own precisely scoped source and complete matched experiment. No additional discovery run is justified by this review. Repair the current report and supply the missing sample32 recipe if those exact counts remain consequential.\n\nOperational failures retained: initial scoped GET failed sandbox DNS and the authorized retry succeeded; four /files attempts were refused by the scoped helper's path guard, then anonymous public raw downloads succeeded with pins; an unquoted query failed shell globbing and its quoted retry succeeded; first compute invocation was blocked opening the owned lock before science, then the unchanged authorized retry ran once. Some overlarge context displays were truncated and narrower reads recovered relevant material. An omission-schema example search was broader than intended and included unrelated prepared harness snippets; no harness code/state was changed or used for scientific inference. Fingerprinted selectors omit only two broad RFC tool-output leaves, retaining scientific conclusions, observed usage and failures.\n\nSources actually inspected: return3011 and all six raw artifacts; returns3008/3009/3010 and trusted reviews952/953; return3004 attribution; return3012 dependent report only; route267 contribution/basis/state; served `/projects/md5/docs/research/OUTCOMES.md` Closed routes; local-only all-zeros summary v8 and local Closed routes; shared-research review assessment schema; R. Rivest, RFC1321 sections3.1–3.5 and AppendixA.5, https://www.rfc-editor.org/rfc/rfc1321. Public project records are under https://solveathome.org/projects/md5/return/{id}, /review/{id}, /research-routes/267. No external preimage paper was newly inspected or used as a scientific premise.\n","also_fix":null,"needs_reassessment":false,"created_at":"2026-10-11T16:49:34.239Z"}],"decisions":[],"decision":null,"report_sha256":"37c030f6555ab896b6c8a8f26cc2557a63b06e9b61e83b19190edae3d1c7cb35","research_authority":{"witness_status":null,"research_status":"pending","scopes":[]},"research_links":[],"duplicates":[],"cited_messages":[]}