{"id":2996,"job_id":6287,"problem_id":6,"lane_id":null,"type":"measure","user_id":73,"model":"claude-opus-5-5","provider":"anthropic","report_md":"# All zeros: the carry gap left by #2993 is closed. Families with a round-2 difference pay a coin flip per shared step (lowest-bit lemma, proved and GPU-checked). Local collisions that rejoin by step 16 reach step 34, but only as isolated pairs on constructed bases.\n\n**Caveats first.** There is no record (platform 11, published 14) and no speed-up. This return answers the gap that #2993 named: carry-propagating realisations of families that change Q13..Q16. With it, the computation-sharing half of open question Q2 is closed for single-chaining-value families, at the scopes stated below. The Q9 tunnel (#2622, #2658) remains the best. It shares steps up to 23 and charges 37 steps per candidate.\n\nNotation as in #2676 and #2993. D = Q'16 − Q16 is the additive difference that a shared round 2 carries forward: sharing gives Q'[t+1] − Q[t+1] = Q'[t] − Q[t].\n\n## C1 (proved, then checked on the GPU): the lowest-bit lemma\n\nLet x, y, z each move by the same additive D ≠ 0 (mod 2^n), and let p be D's lowest set bit.\n- Adding D leaves the bits below p unchanged and flips bit p, whatever the carries above.\n- So G = y ^ (z & (x ^ y)) is unchanged below p. At bit p all three inputs flip, and G's bit p flips exactly when x_p = y_p.\n- Hence dG mod 2^(p+1) is in {0, 2^p}, decided by one coin, and **P[dG = c] ≤ 1/2 for every target c**.\n\nChecks (`lowbit_lemma.cu`, in the GPU sandbox, 1 s):\n- **Exact, n = 8.** All 255 values of D × all 2^24 triples: **0 violations** of the bit-p statement. The maximum of P[dG = c] is exactly 1/2, reached only at D = 128 (the MSB). Excluding the MSB, the maximum is 3/8.\n- **Sampled, n = 32.** All D = ±2^p and ±2^p ± 2^q (2,048 values) × 2^24 random triples: **0 violations**. P(bit p of dG = 1) lies in [0.4996, 0.5004].\n\n## C2 (consequence): every family with D ≠ 0 costs more than Q9, carries included\n\n- **Setting.** Shared steps make Q16, Q17, … carry the same D, so every shared step t ≥ 18 has all three G inputs moved by D.\n- **Two members.** Take two members whose differences D_i ≠ D_j. In member i's frame, apply C1 to D_j − D_i with lowest bit p. Sharing then needs a fixed value of Q^(i)_t[p] ⊕ Q^(i)_(t−1)[p] ⊕ (carry terms), which is a coin on **computed** state bits. Q16 is computed from the fixed m15; Q17 and later always are.\n- **Many members.** N distinct differences branch at ≥ ⌈log2 N⌉ bit levels of their binary trie, so each step needs ≥ ⌈log2 N⌉ independent coins. Over steps 18..T−1 the coins are independent (a fresh Q_t[p] each step).\n- **Probability.** If the computed bits are uniform, P(all N members share through T−1) ≤ N^−(T−18) for a base.\n- **Cost.** Each base trial costs at least one step, so the cost per member is at least N^(T−19) + (61 − T). That exceeds Q9's 37 for every T and every N ≥ 2.\n- **Robustness.** Suppose message modification made all conditions through step 21 free. The bound becomes N^(T−23) + (61 − T): 40 at T = 25, N = 2, and growing from there.\n- The MSB pairs of #2993 are the D = 2^31 case, consistent with this (one coin per step, measured 2^−14, 2^−15, 2^−16).\n\n## C3 (exact SMT, verified): with D = 0, local collisions rejoin by step 16 and share up to step 34\n\nWith D = 0, Q16 and every later state are unchanged. So sharing through T−1 is exactly these conditions:\n- the inner sums of steps 16..18 agree;\n- the words first used at steps 19..T−1 are unchanged;\n- m13, m14 and m15 are the real length words.\n\n`d0_z3.py --real` encodes this exactly (z3 4.13.0). It uses a symbolic base Q1..Q16 (MD5 IV, 52-byte final block: m13 = 0x80, m14 = 416, m15 = 0) and member differences in {0, ±2^p} on Q1..Q15, so carries are free. It requires some change in Q13..Q15.\n\n| p | T = 26 | T = 28 | T = 30 | T = 32 |\n|---|---|---|---|---|\n| 5 | sat (0.8 s) | sat (2.4 s) | sat (6.7 s) | **sat (105 s)** |\n| 20 | sat | sat | sat | unsat |\n\n`verify_d0_pair.py` turns every sat model into two real 52-byte messages (independent code, digest equal to hashlib). All 7 are legal final blocks with Q16..Q19 equal, and they first diverge at the predicted step.\n\nThe T = 32 pair differs only in m6 and m11, one bit each:\n\n- base `fb6b332944c191e78eb5fb8f8a1f6366c33739917067a9753558b6faa91e6dca115f19ef2fa53cea3376e3538915a34d4949279d`\n- member `fb6b332944c191e78eb5fb8f8a1f6366c33739917067a9753558a6faa91e6dca115f19ef2fa53cea3376e353a915a34d4949279d`\n\nTheir states agree from Q16 through Q34, and the first differing inner sum is at **step 34**, the first round-3 use of m11. So it is a collision of MD5 with the standard IV truncated to its first 34 steps. Truncated collisions are implied by known full collisions, so no novelty is claimed. Used as a family it would charge 27 steps per candidate. That is past #2676's 1.194× ceiling, and legitimately so, because that ceiling assumes the state entering step 16 is shared.\n\n## C4 (measured): those pairs are isolated, so they give no family\n\n- **Random real bases.** `d0_fixedbase.py` fixes a real base and asks Z3 for **any** member.\n  - Differences in {0, ±2^p}: **0 of 200 bases** have one, at any of the 32 positions (T = 26, 6,400 checks, each unsat in under 0.1 s).\n  - Differences in {0, ±2^p} + {0, ±2^q}: **0 of 10 bases** have one (all 496 position pairs).\n- **Constructed bases.** `d0_width.py` builds a base together with one member, then enumerates every member of that fixed base, at all 32 positions and every sign pattern.\n  - Bases built at p0 = 5, 12 and 20 (in 8.1 s, 0.4 s and 0.4 s) each carry **exactly 1 member**.\n  - At p0 = 27 no base exists at T = 26.\n- **Dimension count.** At T = 32 only m1, m6 and m11 may differ: 96 free bits against a 128-bit state match, about 2^−32 members expected per base. For smaller T, more words are free, but members are solutions of nonlinear systems (#2676 C4). #2993 found no carry-free generator, and C4 finds no one- or two-bit member on random bases.\n- **Price.** Each extra member costs an SMT solve (0.4 s, about 1.7e10 candidates of GPU Q9 time) to save at most 10 steps once.\n\n## What it means for the track (11 of 32 on the platform, 14 of 32 published)\n\n- For one chaining value with m14 and m15 fixed:\n  - families that keep the state entering step 16 are capped at 1.194× (#2676);\n  - families that change it carry D ≠ 0, priced out with carries included (C1, C2), or D = 0, whose members are isolated local-collision pairs (C3, C4);\n  - carry-free bit-level families stop at step 19 (#2993).\n- **The Q9 tunnel remains the best computation-sharing family.** The record is a throughput race. No structural lead with a stated construction remains under Q2's message-modification half.\n- Proposed status of Q2: answered negatively for single-CV computation sharing. The open parts are CV-varying and multi-block constructions, where #2635 C2 puts the setup at about 2^48 per pair.\n\n## Limits\n\n- C2 assumes uniform, independent computed state bits and a base trial cost of at least one step. Message modification is covered only in the stated robustness form (free through step 21).\n- C4 is measured for member differences of one or two single-bit additive terms per state (any carries) at T = 26. Members with more additive terms per state were not enumerated.\n- Not covered: CV-varying families, multi-block constructions, and layouts other than the 52-byte final block (m13 fixed). For L ≤ 55, m13 is partly fixed in every layout.\n- The `seconds` fields in the outputs are timing; everything else is deterministic for the stated versions and seeds.\n\n## Entry for research/OUTCOMES.md (Closed routes)\n\n| All zeros | Families changing Q13..Q16 with carries (job 6287) | Closed. D ≠ 0: lowest-bit lemma (P[dG = c] ≤ 1/2; checked exactly at n = 8 and on 3.4e10 32-bit samples), so ≥ ⌈log2 N⌉ coins per shared step on computed states and cost ≥ N^(T−19) + 61 − T > 37. D = 0: local collisions sharing to step 34 exist (verified 52-byte pair, 2-bit difference) but only on constructed bases with exactly 1 member; 0 of 200 random bases have one. | this return |\n\n## Sources\n\n- #2993 (job 6277, model T, the named carry gap), #2676 (C2 ceiling, C4 dimension count), #2622 and #2658 (Q9 tunnel and its odds), #2635 (CV-varying cost), #2950.\n- X. Wang and H. Yu, \"How to Break MD5 and Other Hash Functions\", EUROCRYPT 2005: local collisions and message modification, background for C3 and the C2 robustness note (from memory).\n- RFC 1321.\n","patch":null,"cpu_hours":0.3,"hashes":{"d0_z3.py":"1398fd5f901ed19dc79fa872f42de688a81bfc9e1f0ad09e1aca663a95a95891","d0_width.py":"9980aaaa9b57b5fd8e36b07a7a5ef3d1e39e19c14fd4c7fe3c9e97817a2e4e97","d0_fixedbase.py":"fbc3b6879b6382e11dedac65c3c89d309bedb7523ebf3043ad3c2a19099b3ed6","lowbit_lemma.out":"f4a475b1d094d478dcd32031bd620642b658b79c6b42914e85577eb5e83ae186","support_relax.py":"75fb44f826612675d034436e792a94305e31d70df1be77efcd3d0b25554cc6a0","d0_z3_sweep.jsonl":"f522820b85063731da5cd34d0de1d0dca8c2e29efdc8da2b3cc54bdad7a0618a","support_relax.txt":"bb1ee1a9522e6d6208f53f62ffafe569051d1c9f3195eb69fbc37c738bf5c442","verify_d0_pair.py":"36a451b23dd50c26d0b4c63517e1d39082b7fa547f230cd7d1d366759a1e9310","d0_width_T26.jsonl":"452196d739c9bce9d5ce02c1fcbfdd68d25110ce578360c304339dc34777cfc3","lowbit_lemma.cu.txt":"bf84168daa8dbc36d9087853a5fcfd0037aee95772c402ffd6960ffb061f6dc0","lowbit_execution.json":"d6f73057f3fea52020cd0dcadf3d2a329e9c75a8a129f0e28311475a02c8d54f","verify_d0_pairs.jsonl":"f8d43b83c583eb62bb45506c9ee8e7d9fdfbaef7abf9902dd7c18cb7468a400a","fixedbase_T26_200.jsonl":"ecb0cf0b26974ed2112fdacf4ce1a3d74f9e62b199b3f023788cad8c6dfdda1d","fixedbase_T26_r2_10.jsonl":"6835a6f349d28e1be39ad5b665011dbc79f3dd01ecc671c8ab266b37ec8fc85f"},"author_rung":"measured","status":"pending","final_rung":null,"created_at":"2026-10-11T13:02:01.900Z","repo_url":null,"commit":null,"cites":{"files":[],"handles":[],"returns":[2993,2676,2622,2658,2635,2950],"messages":[]},"tokens":{"log":"summary","input":28,"models":{"claude-opus-5-5":56950},"output":56950,"source":"reported","entries":0,"cache_read":4366443,"cache_write":71409,"observed_models":[]},"paper_slug":null,"revision_path":null,"revision_sha":null,"recipe_md":"Fetch each file with `curl -s -H 'Accept: text/plain' \"<server origin>/files/<sha256>?raw=1\" -o <name>` (drop the `job6287_` prefix; rename `lowbit_lemma.cu.txt` to `lowbit_lemma.cu`). Z3 is z3-solver 4.13.0; `seconds` fields are timing.\n1. Lemma: `nvcc -O3 -arch=sm_75 -std=c++17 -o lowbit_lemma lowbit_lemma.cu && ./lowbit_lemma 6287` gives lowbit_lemma.out (about 1 s on an RTX 2080 Ti).\n2. Relaxation: `python3 -I support_relax.py` gives support_relax.txt.\n3. D = 0 pairs: `for T in 26 28 30 32; do python -I d0_z3.py --real --T $T --timeout 300 5 20; done > d0_z3_sweep.jsonl`, then `python3 -I verify_d0_pair.py d0_z3_sweep.jsonl` gives verify_d0_pairs.jsonl (stdlib and hashlib).\n4. Members per base: `python -I d0_fixedbase.py 26 200 62870 60` gives fixedbase_T26_200.jsonl; `python -I d0_fixedbase.py 26 10 62871 60 r2` gives fixedbase_T26_r2_10.jsonl (about 3.5 min); `python -I d0_width.py 26 1 5 20 12 27` gives d0_width_T26.jsonl.","verification":null,"target":null,"finding":null,"human_md":null,"provisional":false,"effects_applied_at":null,"effort":"high","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":null,"research_route_id":null,"verification_plan":null,"verification_fingerprint":null,"review_admitted_at":"2026-10-11T13:02:01.900Z","department_id":"dept_ef09d64fbbd7ddb34ab67f81","run_id":"run_c2ccb63b450f473296a41c24","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":"danieljmt","job_brief":"#2993 closed carry-free bit-level families that change Q13..Q16, but left carry-propagating realisations open. (a) Prove and check on real MD5 a lowest-bit lemma. If Q[t], Q[t-1], Q[t-2] all carry an additive difference D != 0, then for every target c, P[dG = c] <= 1/2 over the base bits at D's lowest set bit, whatever the carries. So each shared round-2 step t >= 18 costs at least one condition on computed states per distinct lowest bit among a family's members. What base-search cost does this force for a family with divergence T >= 25, against Q9's 37 steps per candidate? (b) For D = 0 (Q16 unchanged), Q13..Q15 changes must be absorbed at steps 16..18 by m1, m6, m11, with m0, m4, m5, m9, m10, m14, m15 fixed. Does any family, carries allowed in a bounded window, reach divergence >= 25? What does it cost in conditions on computed states (Q15 and later, since m14 and m15 fix Q15 and Q16)?\n\nWhy this step: This is the named remaining gap of #2993 and the last structural question under #2676's ceiling for Q2. Part (a) needs mostly an argument plus a GPU enumeration over D and c (the person asked for GPU use where it speeds things up). Part (b) is a bounded exhaustive search. Together they would close Q2's message-modification half for every single-chaining-value family, or find the first lever past Q9.\n\nStop when: (a) The lemma is proved, and checked on the GPU over random bases for every single-bit and two-bit D (all positions, all targets), with the implied cost bound for T >= 25 stated. (b) The D = 0 search is exhaustive for carry windows of up to 3 bits per changed state with r = 1, or a sound obstruction is stated. Then report.","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":[],"cited_by":[{"id":2997,"handle":"danieljmt","status":"pending"},{"id":2999,"handle":"danieljmt","status":"pending"}],"route_dependents":[],"research_url":null,"transcript_url":"/projects/md5/return/2996/transcript","files":[{"sha256":"bf84168daa8dbc36d9087853a5fcfd0037aee95772c402ffd6960ffb061f6dc0","name":"job6287_lowbit_lemma.cu.txt","bytes":6183},{"sha256":"f4a475b1d094d478dcd32031bd620642b658b79c6b42914e85577eb5e83ae186","name":"job6287_lowbit_lemma.out","bytes":366},{"sha256":"d6f73057f3fea52020cd0dcadf3d2a329e9c75a8a129f0e28311475a02c8d54f","name":"job6287_lowbit_execution.json","bytes":432},{"sha256":"75fb44f826612675d034436e792a94305e31d70df1be77efcd3d0b25554cc6a0","name":"job6287_support_relax.py","bytes":2979},{"sha256":"bb1ee1a9522e6d6208f53f62ffafe569051d1c9f3195eb69fbc37c738bf5c442","name":"job6287_support_relax.txt","bytes":869},{"sha256":"1398fd5f901ed19dc79fa872f42de688a81bfc9e1f0ad09e1aca663a95a95891","name":"job6287_d0_z3.py","bytes":3860},{"sha256":"f522820b85063731da5cd34d0de1d0dca8c2e29efdc8da2b3cc54bdad7a0618a","name":"job6287_d0_z3_sweep.jsonl","bytes":3266},{"sha256":"36a451b23dd50c26d0b4c63517e1d39082b7fa547f230cd7d1d366759a1e9310","name":"job6287_verify_d0_pair.py","bytes":2774},{"sha256":"f8d43b83c583eb62bb45506c9ee8e7d9fdfbaef7abf9902dd7c18cb7468a400a","name":"job6287_verify_d0_pairs.jsonl","bytes":3408},{"sha256":"fbc3b6879b6382e11dedac65c3c89d309bedb7523ebf3043ad3c2a19099b3ed6","name":"job6287_d0_fixedbase.py","bytes":3578},{"sha256":"ecb0cf0b26974ed2112fdacf4ce1a3d74f9e62b199b3f023788cad8c6dfdda1d","name":"job6287_fixedbase_T26_200.jsonl","bytes":12942},{"sha256":"6835a6f349d28e1be39ad5b665011dbc79f3dd01ecc671c8ab266b37ec8fc85f","name":"job6287_fixedbase_T26_r2_10.jsonl","bytes":691},{"sha256":"9980aaaa9b57b5fd8e36b07a7a5ef3d1e39e19c14fd4c7fe3c9e97817a2e4e97","name":"job6287_d0_width.py","bytes":3351},{"sha256":"452196d739c9bce9d5ce02c1fcbfdd68d25110ce578360c304339dc34777cfc3","name":"job6287_d0_width_T26.jsonl","bytes":1504}],"decided_by_author_handle":false,"reviews":[],"decisions":[],"decision":null,"report_sha256":"0d7f116aa671539304a7666a8871576b05f57ae0a7003875b072d15e7be6bdd2","research_authority":{"witness_status":null,"research_status":"pending","scopes":[]},"research_links":[],"duplicates":[],"cited_messages":[]}