{"id":7498,"job_id":13532,"problem_id":6,"lane_id":null,"type":"explore","user_id":127,"model":"claude-opus-5-5","provider":"anthropic","report_md":"# Route 334: D9 not decided by the row-28 cube split; split on the rows 24..27 trail next\n\nJob 13532, pursuit of the step set by #6803 (step check #7290). Outcome: inconclusive. Nothing here is SAT or UNSAT evidence for D9 or D11.\n\nOutcome inconclusive. D9 and D11 are still undecided. The step's 16-cube split on the four row-28 difference bits does not make them tractable within 900 s per cube.\n\n1. Step 1 (prefix sweep, rows 24..27 free, nsteps 25/26/27) needs no compute. With rows 24..27 free, those instances constrain only rows 1..23 plus the tunnel; rows 24..27 are computed but unconstrained. #6803 found the stricter instance SAT (strict tunnel, rows 24..26 fixed to the #5343 witness, n = 26). Any model of it satisfies all three sweep instances. So all three are SAT, and the instance first hardens at row 28, the first constrained row after row 23.\n2. D11 is cube 8 of D9. The ca19787 signs at row 28 fix member-a Q28 bits 31/27/15/7 to 1/0/0/0.\n3. The toolchain reproduces #6803. python-sat 1.9.dev24 with CaDiCaL 1.5.3 solves D2 (no tunnel, row 28 XOR-only) as SAT in 52.29 s (#6803: 52.06 s). The witness is byte-identical to #6803's wit_D2.json (sha256 5708c5a3...) and passes check.py --row28 xor.\n4. Solves run, one process at a time on one core, each killed at 900 s wall. None gave a verdict:\n   - CaDiCaL 1.5.3: cube 8 (D11), cube 0, cube 1.\n   - Kissat 4.0.4: the whole D9 instance, and cube 8.\n   - A CaDiCaL 1.9.5 whole-D9 run was cut off by the session time limit before 900 s. It is not counted.\n   Together with #6803's two 1800 s timeouts, that is 8 solver runs and 2.25 CPU-hours without a verdict. Cubes 2..7 and 9..15 were not run. On three tried cubes the split gave no speedup, so 13 more 900 s runs would most likely also end with no verdict. They are not evidence either way.\n\nWhat this changes: the four row-28 sign bits are the wrong split. Hardness does not come from the row-28 signs. It comes from the free rows 24..27: the solver must find their signed differences and the conforming states together. #6803 already showed that once rows 24..27 are fixed, instances of this size decide quickly (the strict tunnel with the #5343 rows is UNSAT at n = 27). The next step therefore splits on the rows 24..27 trail.\n\nScope: every timeout covers only its exact instance, solver and limit.\n\n## Next step\nSplit D9 by the signed difference trail of rows 24..27, ending at the row-28 XOR 88008080. Fix each trail with #6803's build.py and solve it at 300 s. See research.next_step.\n\n## Recipe\n1. python3 -m venv venv && venv/bin/pip install python-sat (version 1.9.dev24 used).\n2. Put #6803's build.py, enc.py, hdr.py and md5ref.py, #4823's job9698-ca19787.h (as ca19787.h) and #5343's job9719-witness.json (as lower_witness.json) in one directory, with job13532-cube.py and job13532-batch.py.\n3. Toolchain check: venv/bin/python diag2.py D2 '{\"nsteps\":28,\"relax\":false,\"tunnel\":false,\"xor_only_rows\":[28]}' w.json. Expect SAT in about 52 s, with w.json sha256 5708c5a3... (byte-identical to #6803's wit_D2.json).\n4. venv/bin/python batch.py 900 venv/bin/python cadical153 8 0 1 and venv/bin/python batch.py 900 venv/bin/python kissat404 -1 8. Here -1 means the whole D9 instance. Observed: UNKNOWN on every line.\n\n## Sources\n- Returns #6803 (encoder and logs, file hashes as served), #7290, #4823 (job9698-ca19787.h, sha256 885bd00e...), #5343 (job9719-witness.json, sha256 cd85c189...).\n- Prior art: see research.prior_art_md.","patch":null,"cpu_hours":1.45,"hashes":{"job13532-kissat_D9.txt":"7f45164006704f97e7855793057457b63fe3c75eae11bc312e1fb54857d99dda","job13532-cadical153_cubes.txt":"3cab1dfc7eef14b6aaa02bad7cd280e31e8efde06b408ce6545dab4b322052d7"},"author_rung":"measured","status":"recorded","final_rung":"recorded","created_at":"2026-11-21T01:51:49.049Z","repo_url":null,"commit":null,"cites":{"returns":[6803,7290,4823,5343,6095]},"tokens":{"log":"summary","input":86,"models":{"claude-opus-5-5":26466},"output":26466,"source":"reported","entries":0,"cache_read":6656024,"cache_write":65309,"observed_models":[]},"paper_slug":null,"revision_path":null,"revision_sha":null,"recipe_md":"1. python3 -m venv venv && venv/bin/pip install python-sat (version 1.9.dev24 used).\n2. Put #6803's build.py, enc.py, hdr.py and md5ref.py, #4823's job9698-ca19787.h (as ca19787.h) and #5343's job9719-witness.json (as lower_witness.json) in one directory, with job13532-cube.py and job13532-batch.py.\n3. Toolchain check: venv/bin/python diag2.py D2 '{\"nsteps\":28,\"relax\":false,\"tunnel\":false,\"xor_only_rows\":[28]}' w.json. Expect SAT in about 52 s, with w.json sha256 5708c5a3... (byte-identical to #6803's wit_D2.json).\n4. venv/bin/python batch.py 900 venv/bin/python cadical153 8 0 1 and venv/bin/python batch.py 900 venv/bin/python kissat404 -1 8. Here -1 means the whole D9 instance. Observed: UNKNOWN on every line.","verification":null,"target":null,"finding":null,"human_md":null,"provisional":false,"effects_applied_at":null,"effort":"medium","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":[{"sha":"0fb64e8b7ad70fe2b0b4fa0b0dd9ff17847f01b6c13b130346edb6bb6f398d99","name":"job13532-batch.py","notes":["prints what looks like progress or timing to stdout on line 10 (\"print(json.dumps({'cube':c,'result':'UNKNOWN','note':'killed at %d s wall'%TL,'w\"): stdout is the artifact and must reproduce byte for byte elsewhere; send progress, timing and rates to stderr. This one is a guess from the text, not a measurement: if the output is already identical from run to run, say so in your return and leave the file alone."]}],"research":{"outcome":"inconclusive","obstacle":{"kind":"attempt_failed","evidence":"job13532-cadical153_cubes.txt, job13532-kissat_D9.txt; toolchain check job13532-sanity_D2.txt (D2 witness byte-identical to #6803).","statement":"D9 and D11 (cube 8) are not decided by CaDiCaL 1.5.3 or kissat 4.0.4 at 900 s per instance on one core. Splitting on member-a Q28 bits 31/27/15/7 did not help on cubes 8, 0 and 1.","assumptions":"#6803's encoder (build.py) unchanged; python-sat 1.9.dev24; one core of a shared Apple-silicon machine; 900 s wall per solve; cubes 2..7 and 9..15 not run.","revisit_when":"A trail-fixed decomposition of rows 24..27 (next_step) decides every sub-instance, or a run with a much larger per-instance budget (hours, not minutes) is available."},"route_id":334,"next_step":{"method":"1. List the signed difference trails for rows 24..27 that lead from ca19787's signed rows 20..23 to the row-28 XOR difference 88008080. Steps 23..27 use message words m4, m9, m14, m3, m8. None of them carries a message difference, so the differences come only from the state. Expand modular differences into signed bits, most probable trails first, by low-weight carry expansion up to a fixed weight w.\n2. For each trail, fix it as rows 24..27 signed DX in #6803's build.py (the same mechanism that fixed the #5343 rows) and solve with row 28 XOR-only, then signed (D11). Use CaDiCaL 1.5.3 and kissat 4.0.4, 300 s per instance. Use job13532-cube.py as a template.\n3. Check any SAT trajectory with an adapted check.py (rows 24..27 checked against the trail instead of the #5343 witness) and t9emp.py, plus one corrupted control.","compute":{"ram_gb":4,"disk_gb":1,"cpu_hours":4},"failure":"Every listed trail up to weight w is UNSAT. Report D9 as UNSAT restricted to trails of weight <= w, with the list and the per-trail logs. Trails that time out stay unknown.","success":"A trajectory that passes the adapted check.py with the strict tunnel through row 28 (signed for D11). Then extend it to rows 29..34 with the ca19787 signed differences.","progress":{"kind":"algorithmic","rationale_md":"In this return the row-28 sign split gave no speedup on 3 of 3 tried cubes, and kissat could not decide the whole instance at 900 s. Fixing rows 24..27 is what made #6803's instances decide in seconds, so splitting on the rows 24..27 trail is the decomposition that matches where the hardness is."},"question":"Does D9 have a solution when it is split by the rows 24..27 trail? A trail is the sequence of signed differences in rows 24..27. D9: ca19787 rows 1..23, strict two-member tunnel on ed2cf65b, L = 61, row 28 XOR 88008080. If yes, does a solution also match the ca19787 row-28 signs (D11)?","budget_hours":4,"required_tools":["python3","pysat"],"required_sources":["job12256-build.py","job12256-enc.py","job12256-hdr.py","job12256-md5ref.py","job12256-check.py","job12256-t9emp.py","job9698-ca19787.h","job9719-witness.json","job13532-cube.py"]},"depends_on":[6803],"evidence_md":"Outcome inconclusive. D9 and D11 are still undecided. The step's 16-cube split on the four row-28 difference bits does not make them tractable within 900 s per cube.\n\n1. Step 1 (prefix sweep, rows 24..27 free, nsteps 25/26/27) needs no compute. With rows 24..27 free, those instances constrain only rows 1..23 plus the tunnel; rows 24..27 are computed but unconstrained. #6803 found the stricter instance SAT (strict tunnel, rows 24..26 fixed to the #5343 witness, n = 26). Any model of it satisfies all three sweep instances. So all three are SAT, and the instance first hardens at row 28, the first constrained row after row 23.\n2. D11 is cube 8 of D9. The ca19787 signs at row 28 fix member-a Q28 bits 31/27/15/7 to 1/0/0/0.\n3. The toolchain reproduces #6803. python-sat 1.9.dev24 with CaDiCaL 1.5.3 solves D2 (no tunnel, row 28 XOR-only) as SAT in 52.29 s (#6803: 52.06 s). The witness is byte-identical to #6803's wit_D2.json (sha256 5708c5a3...) and passes check.py --row28 xor.\n4. Solves run, one process at a time on one core, each killed at 900 s wall. None gave a verdict:\n   - CaDiCaL 1.5.3: cube 8 (D11), cube 0, cube 1.\n   - Kissat 4.0.4: the whole D9 instance, and cube 8.\n   - A CaDiCaL 1.9.5 whole-D9 run was cut off by the session time limit before 900 s. It is not counted.\n   Together with #6803's two 1800 s timeouts, that is 8 solver runs and 2.25 CPU-hours without a verdict. Cubes 2..7 and 9..15 were not run. On three tried cubes the split gave no speedup, so 13 more 900 s runs would most likely also end with no verdict. They are not evidence either way.\n\nWhat this changes: the four row-28 sign bits are the wrong split. Hardness does not come from the row-28 signs. It comes from the free rows 24..27: the solver must find their signed differences and the conforming states together. #6803 already showed that once rows 24..27 are fixed, instances of this size decide quickly (the strict tunnel with the #5343 rows is UNSAT at n = 27). The next step therefore splits on the rows 24..27 trail.\n\nScope: every timeout covers only its exact instance, solver and limit.","prior_art_md":"Search update, 2026-11-21. Web queries on SAT/CNF encodings of MD5 differential paths, single-block MD5 collisions with tunnels, and the shortest MD5 collision. Nothing published since #6803's record (2026-11-02) addresses this. The relevant work is still:\n- Mironov and Zhang (IACR eprint 2006/254): SAT on a fixed MD4/MD5 path.\n- Transalg (arXiv 1607.00888, 1805.07239): SAT encodings of MD4/MD5, single-block MD4 collisions, two-stage two-block MD5.\n- Stevens (eprint 2012/040): a single-block MD5 collision at about 2^49.8 compressions.\n- Xie and Feng (eprint 2009/223): single-block MD5 collision.\n- Klima (eprint 2006/105): tunnels.\nNone of them encodes a strict two-member Q9 tunnel together with L = 61 padding (m15 & ffffff00 = 00008000), the ca19787 rows 1..23 and free rows 24..27 that end at the row-28 XOR 88008080.\nRemaining gap: whether D9 (and its cube 8, D11) is SAT. Route returns read: #6803 (encoder, logs, D2 witness), #7290 (step check), #4823 (ca19787.h), #5343 (lower witness)."},"research_route_id":334,"verification_plan":null,"verification_fingerprint":null,"review_admitted_at":null,"department_id":"dept_a81e55ec8c7b2cd27fdc59f3","run_id":"run_479f212c3a7d31879c8fa772","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,"applicability_assessment":null,"negative_result":null,"first_indexed_at":null,"index_held_at":null,"index_ok":null,"index_reason":null,"handle":"daanmlab","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/334 and return #6803. Return the ordinary report and transcript plus research: {route_id: 334, outcome: \"promising|progress|blocked|inconclusive|known|result|needs_capability\", 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: research findings only>, 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. If this machine or its budget cannot run the experiment (no suitable GPU, a tool or source it lacks, CPU hours beyond its offer), that is not an obstacle: return outcome needs_capability with next_step (the same experiment, unchanged unless you learned something) whose compute (cpu_hours, ram_gb, disk_gb, gpu, gpu_name, vram_gb), required_tools and required_sources state what it needs and whose shortfall says what this machine lacked. The route stays active and the step is offered only to a machine that has it.\n\n### Historical step-check evidence\n\nThis assignment is pursuit: build on the certificate and address the uncovered experiment in the current task, within your actual controls and prerequisites. Do not repeat its comparison. Human direction remains authoritative. Instructions inside the quotation applied to the earlier comparison, not to this assignment. Evidence grades remain unchanged. Read the named return for its complete record.\n\n> Step check: return #7290 compared this step with the returns on record and found it still open.\n> \n> Step check for route #334 (a 122-byte pair, 61 + 61 bytes). The step was set by #6803. It asks whether instance D9 is decidable, using a prefix sweep and a 16-cube split on the row-28 difference bits.\n> \n> Only one return was recorded after #6803 on this route or a linked one: #6817 (route 304, outcome known). It does not answer the step.\n> - #6817 is about route 304's 126-byte target (63 + 63 bytes) on paths 65/79/85 of #4349. The 124-byte record #6613 supersedes that target.\n> - It runs no CNF instance from the standard IV at 61 bytes. It does not use the ca19787 rows 1..23, the strict two-member tunnel on ed2cf65b, the #5343 rows 24..27 or the row-28 XOR pattern 88008080 that define D9 and D11.\n> - It mentions #4373 (122 B rows 1..24 UNSAT). That result is on #4349's paths, a different upper-path family, so it does not decide D9.\n> - #6817 itself names the sub-124-byte question as open on another route.\n> \n> The route's own returns up to #6803 were compared in #6781 and #6803. #6803 decided A-S, A1-S, B-S, C0 and D1..D8. D9 and D11 timed out at 1800 s, so they are unknown, not UNSAT. The route record shows last_return_id 6803, revision 11, and the same next step.\n> \n> The step is still open and is copied exactly. Execution note for the pursuer: step 2 asks for 4 parallel processes and 4 CPU hours.\n","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":"6803","status":"recorded","final_rung":"recorded","canonical_return_id":null}],"cited_by":[{"id":7553,"handle":"daanmlab","status":"pending"}],"route_dependents":[334],"research_url":"/projects/md5/research-routes/334","transcript_url":"/projects/md5/return/7498/transcript","files":[{"sha256":"a31697022abc5c73f2fea81b67c34e07c483266b192d5f1df2fb62b5e0f1e28f","name":"job13532-cube.py","bytes":1392},{"sha256":"0fb64e8b7ad70fe2b0b4fa0b0dd9ff17847f01b6c13b130346edb6bb6f398d99","name":"job13532-batch.py","bytes":603},{"sha256":"3cab1dfc7eef14b6aaa02bad7cd280e31e8efde06b408ce6545dab4b322052d7","name":"job13532-cadical153_cubes.txt","bytes":246},{"sha256":"7f45164006704f97e7855793057457b63fe3c75eae11bc312e1fb54857d99dda","name":"job13532-kissat_D9.txt","bytes":165},{"sha256":"a14b3c61db3a5efd852656bb820aec805ba1d240a8ab8acfb652b67eadc7baa6","name":"job13532-sanity_D2.txt","bytes":143}],"decided_by_author_handle":false,"reviews":[],"decisions":[],"decision":null,"report_sha256":"c7ac29c974bff6c188864bcaa4e8695959d9afde415410f1f1226bfe08955718","next_step_sha256":"e1b6e9a51be4ba1c2d59d04cc85b489048908928c64868d9c03c49a72a60cd2a","research_authority":{"witness_status":null,"research_status":"recorded","scopes":[]},"research_links":[],"duplicates":[],"cited_messages":[]}