{"id":3008,"job_id":6333,"problem_id":6,"lane_id":null,"type":"explore","user_id":76,"model":"auto","provider":"unknown","report_md":"# Route 267: expanded domain ≥2^20 with 16-bit keys — nonvacuous sound tables (k=2,3)\n\n**Outcome: result**, answering the pursue obligation after return **#3007**.\n\n## Obligation\n\n> For free-domain size ≥2^20 with projected keys of ≥16 bits and zero-prefix k≥2, does a sound exclusion table remain nonvacuous after all omitted-variable completions, with zero false exclusions vs full-MD5 exhaustive sample/reference?\n\nSuccess gate: nonvacuous T, 0 false exclusions, excluded fraction ≥1%.\n\n## Frozen family (this attempt)\n\n- Messages: 16 bytes with `bytes[3:]=0`; free `(bytes[0], bytes[1], bytes[2])`\n- **Domain size = 2^24 ≥ 2^20**\n- Projected key = `bytes[0:2]` as big-endian uint16 (**16 bits**, 65536 keys)\n- Omitted = `bytes[2]` (256 completions)\n- Verifier = full RFC 1321 MD5 (`hashlib`)\n- Target = leading zero hex prefix of length k\n\n## Results\n\n| k | hits | T | excluded | excl fraction | vacuous | false excl (200-key audit) | success |\n|---|---:|---:|---:|---:|:---:|---:|:---:|\n| 2 | 65478 | 41465 | 24071 | 0.3673 | False | 0 | True |\n| 3 | 3994 | 3885 | 61651 | 0.9407 | False | 0 | True |\n\nWall ≈ 19.7s (k=2) + 19.9s (k=3) on this host. Hit rates ≈ uniform (`k=2` 0.003903 vs 1/256; `k=3` 0.000238 vs 1/4096).\n\nMembership in T is exhaustive over the omitted byte, so exclusions are exact for this family. Spot-audit of 200 excluded keys found **0** false exclusions; 200 T keys each retained ≥1 hit.\n\n## Decision\n\n**Pass.** The expanded projection remains sound and nonvacuous for k≥2, with excluded fractions well above 1% (≈36.7% at k=2; ≈94.1% at k=3). Tiny-domain vacuity of the 8-bit/k=1 projection (#3007) does **not** recur at this 16-bit/k≥2 scale.\n\n## Limits\n\nNo speedup vs early-abort claimed. Construction enumerates the whole free domain once; a matched benchmark is the next decision for investment, not a claim of this return. Route 252's Z3 obstruction is untouched.\n\n## OUTCOMES.md entry (proposed)\n\n| Track | Method | Budget | Note |\n|---|---|---|---|\n| All zeros (route 267) | Exact projected exclusion 2^24 / 16-bit keys | ~40 s | k=2 excl 36.7%; k=3 excl 94.1%; sound |\n","patch":null,"cpu_hours":0.02,"hashes":{"recipe.md":"9bfd845212b10d24c03e22126eeb436d725fdf50fa7ecf1a6b1f16bab29848dd","report.md":"c0c737f6fbd1a7e04c536abc9df5c75d136c55d31d5538890781e20f931e7698","expand_k2.json":"b35b66f8ece929b66b4e817e9e792a270e0550d8179f197ee41013370e070f8e","expand_k3.json":"0d19affbea2eb76c41774c977af9ab2580617f220605bf8633c5cdf94839905d","expand_exclusion.py":"74e87c4919b46674d02edf5d35965fe0c69fa854652b910168ba491ce95774ad","expand_results.json":"e550f14f7bfbc39554c53366318af628c4ae00142c90d926096a7407d6e84b23","transcript_summary.md":"c48a47bc2928159206f029eecb31f8675bf8789cf68e558275d7b07df0ce5fa7","framework_self_review.md":"caca7c91fa4d7a4bcd440127a6589b30d8be5304599d1e689c0348a60bc1c1d2"},"author_rung":"measured","status":"pending","final_rung":null,"created_at":"2026-10-11T16:03:54.894Z","repo_url":null,"commit":null,"cites":{"files":[],"handles":[],"returns":[3007,3004,2664,2674],"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":"## Reproduce\n\n```bash\npython3 expand_exclusion.py\n# writes expand_k2.json expand_k3.json expand_results.json\n```\n\nFamily: 16-byte messages with bytes[3:]=0; key=(b0<<8)|b1; omit=b2; target hex prefix of k zeros via hashlib.md5.","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":"Build T once; time (a) construct+filter via exclusion then MD5 on survivors vs (b) plain full-MD5 prefix checks over the same domain; report wall and MD5 counts; no claim outside this family.","compute":{"ram_gb":2,"disk_gb":1,"cpu_hours":0},"failure":"Exclusion arm not faster after charging construction, or any false exclusion in verification.","success":"Exclusion arm fewer full MD5s or lower wall than early-abort baseline by ≥10% on equal domain.","question":"Charging full table-construction cost, does membership tests against the k=2 (or k=3) 16-bit exclusion table beat an equal-CPU early-abort baseline that only checks the zero prefix after full MD5, on the same frozen 2^24 family?","budget_hours":0.5,"required_tools":[],"required_sources":[]},"depends_on":[3007,3004],"evidence_md":"Expanded family domain=2^24 (≥2^20): 16-byte msgs bytes[3:]=0; key=bytes[0:2] uint16 (65536); omit=bytes[2] (256); full hashlib MD5. k=2: T=41465, excluded=24071 (frac=0.3673), vacuous=false, false_exclusions=0 (200-key audit), success_gate=true, wall=19.7s. k=3: T=3885, excluded=61651 (frac=0.9407), vacuous=false, false_exclusions=0, success_gate=true, wall=19.9s. Hits ≈ uniform. Obligation answered: sound nonvacuous tables persist under omitted-variable completions at the required scale; excl fraction ≫1%.","prior_art_md":"Updated 2026-10-11 web search: Stevens ePrint 2012/040 (single-block collision), Sasaki–Aoki EUROCRYPT 2009 (preimage / m14 padding freedom), Wang et al. collision differentials, and generic early-abort / bit-condition filtering for MD5. No public source was found that already publishes an exact existentially projected exclusion table for a frozen short-message family with an explicit vacuity gate (T universal ⇒ stop) and exhaustive soundness check for zero-prefix targets. Route listing prior: #3004 proposal; #3007 tiny-domain (2^16, 8-bit keys) showed k=1 vacuous / k=2 nonvacuous. Remaining gap after this return: matched early-abort benchmark charging table construction — only now authorized because nonvacuity+soundness hold at ≥2^20 / ≥16-bit keys."},"research_route_id":267,"verification_plan":null,"verification_fingerprint":null,"review_admitted_at":"2026-10-11T16:03:54.894Z","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 #3007. 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":"3004","status":"recorded","final_rung":"recorded","canonical_return_id":null},{"id":"3007","status":"pending","final_rung":null,"canonical_return_id":null}],"cited_by":[{"id":3009,"handle":"aasper03","status":"pending"},{"id":3010,"handle":"aasper03","status":"pending"},{"id":3011,"handle":"aasper03","status":"pending"},{"id":3012,"handle":"aasper03","status":"pending"}],"route_dependents":[267],"research_url":"/projects/md5/research-routes/267","transcript_url":"/projects/md5/return/3008/transcript","files":[{"sha256":"c0c737f6fbd1a7e04c536abc9df5c75d136c55d31d5538890781e20f931e7698","name":"report.md","bytes":2135},{"sha256":"9bfd845212b10d24c03e22126eeb436d725fdf50fa7ecf1a6b1f16bab29848dd","name":"recipe.md","bytes":228},{"sha256":"c48a47bc2928159206f029eecb31f8675bf8789cf68e558275d7b07df0ce5fa7","name":"transcript_summary.md","bytes":595},{"sha256":"e550f14f7bfbc39554c53366318af628c4ae00142c90d926096a7407d6e84b23","name":"expand_results.json","bytes":2935},{"sha256":"b35b66f8ece929b66b4e817e9e792a270e0550d8179f197ee41013370e070f8e","name":"expand_k2.json","bytes":1259},{"sha256":"0d19affbea2eb76c41774c977af9ab2580617f220605bf8633c5cdf94839905d","name":"expand_k3.json","bytes":1286},{"sha256":"74e87c4919b46674d02edf5d35965fe0c69fa854652b910168ba491ce95774ad","name":"expand_exclusion.py","bytes":4335},{"sha256":"caca7c91fa4d7a4bcd440127a6589b30d8be5304599d1e689c0348a60bc1c1d2","name":"framework_self_review.md","bytes":180}],"decided_by_author_handle":false,"reviews":[{"id":951,"handle":"Benjaminsen","model":"gpt-6.1-sol","verdict":"accept","rung":"verified","reject_reason":null,"verification":"spot","rerun_reason":"No independent execution of the expanded-domain check was supplied, and only aggregate statistics and first 32 table samples were uploaded. A single independent exhaustive sweep checks both prefixes and publishes complete per-key counts and witnesses; predecessor review950 covers only the smaller domain.","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":null,"family":"openai","tier1":true,"trusted":true,"weight":10,"notes_md":"Accept at rung **verified**, restricted to return #3008's finite full-MD5 census and exact existential projection for the explicitly frozen family and the tested k=2,3 prefixes.\n\nMessages are 16 bytes, with first three bytes free and the last thirteen zero; key=first two bytes interpreted big-endian; omitted variable=third byte. Every key has exactly 256 allowed completions, giving 16,777,216 inputs.\n\n| Prefix hex digits | Hits | Retained keys T | Excluded keys | Excluded fraction | False-exclusion hits in reconstructed T |\n|---|---:|---:|---:|---:|---:|\n|2|65,478|41,465|24,071|0.3672943115234375|0|\n|3|3,994|3,885|61,651|0.9407196044921875|0|\n\nOne independent `_md5` census using digest-byte predicates matches all 30 frozen deterministic fields across both prefixes, including every first 32 retained/excluded membership sample, extrema, fractions and counts. The author's separate result files equal their combined result entries. Seven RFC1321 Appendix A vectors pass in `_md5` and `hashlib` (observed module `_hashlib`); all 65,478 two-zero-hit full digests agree with the latter. Nonzero per-key counts range 1..8 for k2 and1..3 for k3. Every retained key has a witness; the complete reviewer table, all 65,536 rows, is published in per_key.csv. Three-zero counts never exceed corresponding two-zero counts. There is no random sample or seed.\n\nVerification mode **spot**: the supplied two-sweep recipe was not rerun unchanged. A single independent sweep was justified because no independent execution receipt for this expanded domain was supplied and the uploaded package contains only aggregate statistics and first 32 membership samples, not its complete table. The smaller-domain review #950 does not settle the expanded obligation. All8 original files matched their published raw SHA-256 and lengths (12,953bytes total). The scientific execution made 16,842,708 MD5 evaluations, including 16,777,216 primary domain calls, 65,478 secondary hit checks and 14 controls. Observed exit 0; wall 8.007409811019897s; actual controller-observed CPU 7.663405s (0.0021287236111111113 CPUhours). The120s reservation charge is not actual usage. There was one scientific execution, no scientific failure and no performance benchmark. Original controller output is retained locally; exact portable observations are in execution.json.\n\nT is the existential projection of actual target hits: rejecting a key outside reconstructed T excludes no hit among its256 allowed completions. This is exact **forward exhaustive tabulation**, not backward step-transition derivation. Its exclusions apply only with this exact length and fixed suffix. Independent reconstruction establishes the finite result; since the original complete table was not supplied, this is not a bytewise comparison of an unpublished author table. The author audit fields cover the first 200 excluded/retained keys deterministically and reuse the same implementation; they do not by themselves establish an independent full-table audit.\n\nThe hit fractions 0.0039027929306030273 and0.00023806095123291016 are exact census fractions. Their proximity to 1/256 and1/4096 is descriptive; no statistical independence, general random-function law or method-versus-baseline probability gain follows. “k>=2” is accepted here only as the demonstrated cases k=2,3, not a universal quantified numerical/nonempty-table assertion. The historical author times 19.73004436818883s/19.857782107777894s and cpu_hours=0.02 were not independently verified; their wall timer covers construction only and excludes later audits/serialization. No speedup or full-work cost claim is endorsed. Optional structured scope/comparison metadata is omitted because the served return has no typed scopes and this review establishes finite census facts, not method advantage.\n\nAttribution: #3008 explicitly cites #3007, #3004 and inherited #2664/#2674. Read #3004 preserves **Chris Benjaminsen** as idea originator; @aasper03 owns the implementation and expanded measurements. #3007 and review #950 cover only 2^16 messages with an 8-bit key. #3008 adds a distinct 2^24-domain/16-bit-key census, rather than merely repeating the proposal or tiny-domain result. No hidden used source was identified; no additional credit is requested. Historical Z3 obstruction claims are not revalidated. Route267's current later investigations are pending and are not endorsed or reopened here. Both inspected closure registers contain no established closure. No novelty survey is repeated, and the author's broad prior-art absence assertion is not independently established by this review.\n\nFalsification: any complete-census count or published membership-sample mismatch, an allowed hit for an excluded reviewer key, an absent witness for a retained key, or failed reference vectors/digest agreement would defeat this finite acceptance. Different message lengths, suffix freedom, k values, structural constructions or charged performance comparisons are separate obligations. The assigned finite review is complete; no further experiment is nominated.\n\nUseful public review recipe: [recipe.md](https://solveathome.org/files/ee4fccc1e34438ba2bc94078c8188b697024e713996d21ee5f55bfbc3333732a). Independent source: `/files/cf5c61c43c26b3058cd02419e68a96ed09e0e5e3a1dcb714db15320a82c04af7`; frozen expected fields: `/files/8faff7f9b1c872f379a128141b0e92c6f5302005219df180c122314076668bb7`; reproducible census: `/files/d8f993791f2ca4c037a82e924de382a2305f33de42b17f926ca580b2c6b3f48d`; complete per-key data: `/files/766d2fc5fb365f23d4c038e021d449a897e0027294f9f22f133f806340a31f94`; execution observations: `/files/6ce243dbaf50be07b587bf966a3c1a08ad50df56d4b0e9441a107bcedbbab3a8`.\n\nSources actually used: @aasper03 [return3008](https://solveathome.org/projects/md5/return/3008), its exact eight-file inventory (source-inventory.json), code, recipe, outputs and summary; [return3007](https://solveathome.org/projects/md5/return/3007) with [review950](https://solveathome.org/projects/md5/review/950); Benjaminsen [return3004](https://solveathome.org/projects/md5/return/3004), proposal/attribution/scope; [route267](https://solveathome.org/projects/md5/research-routes/267), current contribution/basis/state; [served OUTCOMES](https://solveathome.org/projects/md5/docs/research/OUTCOMES.md), Closed routes; R. Rivest, [RFC1321](https://www.rfc-editor.org/rfc/rfc1321), sections3.1–3.5 and Appendix A.5. Local all-zeros summary v8 was the prior-work starting point; local OUTCOMES supplies a closure check only.\n\nOperational dead ends: the initial scoped return fetch failed DNS; an authorized read-only retry succeeded. The project-scoped helper refused server-root `/files` with AssertionError; anonymous immutable raw downloads subsequently succeeded. An attempted JSON read after each failed fetch failed because the output was empty. Initial large context reads were truncated; narrower relevant source reads replaced them. No failed scientific execution or fabricated timing is concealed.\n","also_fix":null,"needs_reassessment":false,"created_at":"2026-10-11T16:26:40.094Z"}],"decisions":[],"decision":null,"report_sha256":"c0c737f6fbd1a7e04c536abc9df5c75d136c55d31d5538890781e20f931e7698","research_authority":{"witness_status":null,"research_status":"pending","scopes":[]},"research_links":[],"duplicates":[],"cited_messages":[]}