{"id":561,"job_id":1184,"problem_id":1,"lane_id":5,"type":"explore","user_id":1,"model":"deepseek-v4-flash","provider":"deepseek","report_md":"# Job #1184 — Rescue of route #18: the obstruction is algorithm-scoped, and the prune it asks for provably cannot fire\n\nAttempt `6e99b1d7294475ef9f8b4d84cc698401` · type **explore** · rescue · lane infinitude.\nAuthor rung: **heuristic** for the investment decision; the two negative results below are\n**proved** (exact integer arithmetic, reproduced by the attached script), and one of them also\nreports a **measured** validation on small instances.\n\n## Decision\n\n**Promising**, on a changed figure of merit, with one bounded next experiment. Two repairs that\n`revisit_when` invites are refuted here so they are not funded, and the surviving branch is\nidentified.\n\n## 1. What the obstruction is, stated exactly\n\nReturn #473's `scoped_obstruction` is a count of expanded nodes for **one algorithm**: 19-way\nbranching on unassigned slots with only assigned-colour pair deletions, no learning, no global\nprune, no quotient. I reproduced its numbers exactly (`rescue_probe.out`, part A):\n`1, 19, 342, 5814, 93024, 1395360`, sum **1,494,560**, i.e. 7.47× the 200,000 cap.\n\nThe structural reading matters more than the total. Those are `1` and the falling factorials\n`(19)_k` = `19·18·…·(19−k+1)`: they count prefixes whose colours are **pairwise distinct**. So at\ndepth k the tree is wide because the k already-used colours are (almost) never reusable. That is a\nstatement about the *thinness of the pair lists*, not about unsatisfiability. Two consequences the\nobstacle itself concedes and this assignment makes explicit:\n\n* The count bounds only a **complete UNSAT enumeration**. On a satisfiable instance the same\n  premise — nearly every fresh colour legal at every node — is precisely what makes a witness\n  reachable in at most 51 assignment steps with no backtracking.\n* Therefore \"1,494,560 > 200,000\" is not evidence that the negative is expensive; it is evidence\n  that the instance is **loose**. The correct response is to decide satisfiability, not to widen\n  the cap.\n\n## 2. The prune family `revisit_when` asks for cannot fire here — proved\n\n`revisit_when` item (a) requests \"a specified sound global prune\". The canonical member of that\nfamily is the per-colour **capacity / clique-cover** certificate, and it is both sound and cheap,\nso it had to be tested before being proposed. Model: n slots, C colours, and for each pair the set\nof colours that may not own both, of size ≤ s; `H_c` = graph on slots with an edge exactly when\ncolour c may not own that pair. A colour class for c is an independent set of `H_c`, so colour c\nowns at most `α(H_c)` slots, and exhibiting a clique cover of `H_c` with `k_c` cliques *certifies*\n`α(H_c) ≤ k_c` in `O(k_c·n)` time. If `Σ_c k_c < n` the instance is UNSAT with that cover as the\ncertificate.\n\n**Result (part B).** With `n = 51`, `C = 19`, `s = 3` (route 18's own bound), so at most\n`E = 3·C(51,2) = 3825` forbidden-colour incidences spread over 19 colours:\n\n```\nk_c = cc(H_c) = chi(complement of H_c)  >=  n^2 / (n + 2 e_c)          [chi >= n^2/(n^2-2m), m = C(n,2)-e_c]\nJensen over colours (f(e) = n^2/(n+2e) is convex):\n   sum_c k_c  >=  C · n^2 / (n + 2E/C)  =  19 · 2601 / 453.6  =  108.94\n```\n\nA capacity refutation needs `Σ_c k_c ≤ n − 1 = 50`. So **every** per-colour clique-cover\ncertificate on the D51 support has at least **109** pieces against a budget of 50, and no\ncertificate in this family exists. The same bound is `266.8` at s = 1, `154.7` at s = 2, `84.1` at\ns = 4 and `57.7` at s = 6 — it only stops excluding the family from s ≈ 10 upward. This is a\nproperty of the sparsity the route itself uses, so it is not an accident of D51.\n\n**Exact scope.** This refutes the *per-colour independent-set-upper-bound* family only. It says\nnothing against joint/subset relaxations, clause learning, DAG proofs, or any arithmetic proof.\nIt also does not touch the count in §1, which remains a correct bound for its own algorithm.\n\n**Measured validation (part C).** The certificate checker was implemented and run against brute\nforce on 420 small random instances (n ≤ 7, C ≤ 3, s = 1..3). It never certified a satisfiable\ninstance (`C_sound: true`), and its fire counts track clique-like instances: at s = 1 it certified\n24 of 48 brute-force-UNSAT instances, at s = 2 80 of 83, at s = 3 140 of 140. Two notes on scope:\nthis sample is *tiny* and does not by itself establish the D51 fire rate — §2 does that by\ninequality, not by sampling; and the sample's last row is clique-like, not thin, so it is not\nevidence about route 18's regime. One bug was found and fixed during this validation: an\nindependence test written as `adj[u] & adj[v]` fires on shared neighbours and produced 63 false\ncertificates; after correcting it to the `u–v` edge bit the checker is sound. This is the reason\nthe soundness check is in the recipe rather than taken on trust.\n\n## 3. The changed ingredient (prior art search)\n\nThe obstacle's own prior-art ledger cites Beyersdorff–Galesi–Lauria for tree-like resolution\nlower bounds on PHP, and correctly notes the D51 formula is not PHP. The search for the *changed*\ningredient found the missing half of that picture:\n\n* **S. Buss, T. Pitassi, \"Resolution and the Weak Pigeonhole Principle\", CSL'97, LNCS 1414,\n  Springer, 1998, pp. 149–156, DOI 10.1007/BFb0028012** — the entry (*not* the asymptotic theorem)\n  is the right analogue: it gives **upper bounds on resolution proofs of the weak pigeonhole\n  principle and lower bounds for tree-like resolution proofs**. The separation is exactly the one\n  that matters here: size (DAG, with learning) behaves very differently from tree-like search.\n  Atserias–Pitassi, \"Lower Bounds for the Weak Pigeonhole Principle and Random Formulas beyond\n  Resolution\" (FOCS 2002), was located as the boundary case and not read beyond its record.\n* The D51 instance is **easier than weak PHP**: weak PHP forbids *every* same-hole pair, while the\n  owner lists permit most equal-colour pairs (only ≤ 3 shared colours per pair). So a small\n  certificate is more plausible here than in weak PHP, and the tree-like lower bounds that the\n  route's ledger cites do not transfer to a size-based figure of merit.\n\n**Exact remaining gap (unchanged by this assignment):** no located source states the *size* of a\nresolution/Farkas refutation for the frozen D51 owner instance, or for the class of \"partition into\nindependent sets with per-colour conflict graphs\" instances of this thin shape. The LP/cover solve\nis still unperformed — return #472 records \"No frozen census/LP/cover solve performed\", which is\nthe single largest hole in this route and the direct object of the next step.\n\n## 4. The rescue\n\nChange the figure of merit from *expanded tree states* to *size of an independently checkable\nobject*, and decide satisfiability before seeking any negative. The obstacle's own premise makes\nthis the cheapest correct route, and the Buss–Pitassi separation is the evidence that a\nsize-based target is the right one for a weak-pigeonhole-shaped formula.\n\n**Weaker requirement (also available, if the sweep resists).** Instead of a complete checked\nUNSAT proof of the whole frozen D51 support, prove the phase-cover statement on a sub-window with\nfewer slots. Exact owner equivalence is preserved, the checked cost falls with the slot count, and\nit needs no new method.\n\n**Distinct bounded next experiment (next_step).** See the structured field below: build the census\nthat was never built, decide SAT/UNSAT with learning enabled, and adopt witness-or-certificate-size\nas the cost measure. Every branch of it is a *bounded* test, none of them can be blocked by the\n1,494,560 count, and the checker for each output is specified.\n\n## Execution, files and recipe\n\n* Script: `.solveathome/runs/mvDkQmElejQpQBP9mH3VAA/work/rescue_probe.py`\n  sha256 `7dfddb2d27c61479efb6511bb3bd6705eb3e9bc7081852631d35d5c6133b2cef` (uploaded).\n* Output: `rescue_probe.out` sha256\n  `ccf4bd923c9c07f23eff7e439fa563923ff279129bee95558cc710eebcdfc1c0`. Deterministic (single fixed\n  seed `20260915` in part C); no randomness in parts A and B. Runtime 0.09 s.\n* No published computation was rerun: the 1,494,560 count is reproduced only as an arithmetic\n  identity to fix its reading, and no D51 census, LP or source curve was re-executed.\n\n**Transcript.** Attached, scrubbed as data from this harness's session log, cut from your\ninstruction that opened this assignment. Removed: the account token (prefix `sah_…`), provider\n`userId`/`userEmail` on every line, installation identifiers, absolute home-directory paths, and\nthe private solveathome session id. No per-turn token usage is attached: this harness records only\n`contextTokenCount` and `stepCreditsUsed`, so usage is unknown and is omitted rather than\nestimated.\n\n**Caution for the person.** As in the previous return, this harness's CLI log is not a format the\nserver recognises, so no tokens are credited from this transcript; and 9 of your returns are still\nqueued awaiting a reviewer on another model, since a deepseek-flash agent cannot review its own kind.\n","patch":null,"cpu_hours":0.01,"hashes":{"rescue_probe.out":"ccf4bd923c9c07f23eff7e439fa563923ff279129bee95558cc710eebcdfc1c0"},"author_rung":"heuristic","status":"recorded","final_rung":"recorded","created_at":"2026-09-15T09:20:15.691Z","repo_url":null,"commit":null,"cites":{"files":["7dfddb2d27c61479efb6511bb3bd6705eb3e9bc7081852631d35d5c6133b2cef"],"handles":[],"returns":["472","473",473],"messages":[]},"tokens":{"log":"unknown","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":"# Verification recipe\n\nReproduces every concrete output this return reports. Python 3 stdlib only; no solver needed.\nPaths are relative to the repository root.\n\n## 1. The probe (parts A, B, C)\n\n```bash\ncd .solveathome/runs/mvDkQmElejQpQBP9mH3VAA/work\npython3 rescue_probe.py > rescue_probe.out\nsha256(rescue_probe.py)  = 7dfddb2d27c61479efb6511bb3bd6705eb3e9bc7081852631d35d5c6133b2cef\nsha256(rescue_probe.out) = ccf4bd923c9c07f23eff7e439fa563923ff279129bee95558cc710eebcdfc1c0\n```\n\nDeterministic: parts A and B are exact integer/Fraction arithmetic with no randomness; part C uses\na single fixed seed (`random.Random(20260915)`). Runtime ~0.09 s, stdout is the artifact, nothing\nis printed to stderr. Expected headline values:\n\n| Field | Expected |\n|---|---|\n| `A_sum` | `1494560`, equal to the reported count, `A_matches_reported: true` |\n| `A_counts` | `[1, 19, 342, 5814, 93024, 1395360]` = 1 and the falling factorials `(19)_k` |\n| `B_route18_s3.lower_bound_sum_cc` | `108.94…` (an irrational-free exact Fraction; printed as float) |\n| `B_route18_s3.can_fire` | `false` (needs `<= 50`) |\n| `C_sound` | `true` |\n\nThe soundness assertion is `C_sound`. It is the load-bearing check: an earlier version of the\nindependence test wrote `adj[u] & adj[v]` (true for shared neighbours) and returned\n`certified=63 > brute_unsat=48` at s=1, i.e. it certified satisfiable instances. If a future edit\nmakes `C_sound` false, the certificate construction is wrong and part B's bound must be re-checked.\n\n## 2. What part B claims, and how to falsify it\n\nPart B is an inequality, not a sample. It uses `cc(H) = chi(complement of H) >= n^2/(n^2-2m)` with\n`m = C(n,2) - e_c` edges in the complement, then Jensen over colours since `f(e)=n^2/(n+2e)` is\nconvex. To falsify it: exhibit the D51 pair lists, compute `cc(H_c)` exactly per colour, and show\n`sum_c cc(H_c) <= 50`. That is the single check that would reopen the capacity-prune branch, and it\nrequires the census that does not yet exist.\n\n## 3. Scope of what is *not* claimed\n\nNo D51 census, LP or source curve was executed here, and no published computation was rerun. The\n1,494,560 count is reproduced only as an arithmetic identity, to fix its structural reading. Parts\nB and C say nothing about joint/subset relaxations, clause learning, DAG proof size or arithmetic\nproofs.\n\n## Cost\n\n0.09 CPU-seconds for the probe; the rest of this assignment was retrieval and reading. Well inside\nthe attempt's envelope (75% of the machine, 16 GB, 4 CPU-h, 5 GB).","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":"promising","route_id":18,"next_step":{"method":"Decide, do not enumerate; measure the size of an object, never the size of a tree. (0) Build the census that was never built (return #472: 'No frozen census/LP/cover solve performed'): the D51 slot-owner instance as n=51 slots, C=19 colours, and for every slot pair the exact <=3 shared/forbidden colour set, exported as DIMACS CNF with one variable per (slot,colour) pair, at-most-one colour per slot, and one negative binary clause per forbidden (pair,colour) - about 51 + 51*171/2 + 3*1275 clauses. Publish the CNF and its sha256 so the instance stops being informal. (1) With learning enabled (CDCL), which the obstruction's own assumptions exclude, decide SAT/UNSAT under a conflict budget rather than an expanded-state budget, and report CONFLICTS and learned-clause count, not nodes. (2) If SAT: emit the 51-slot witness and verify it with a checker that tests all pair constraints in O(#pairs); the cost target is then met by a witness and the 1494560 tree count is irrelevant. This is the branch the obstruction's own premise (>=19-k fresh colours legal at every shallow node) favours, so run it first. (3) If UNSAT: emit the refutation and report its SIZE in clauses plus a quadratic-time checker, and compare that size with 1494560 - per Buss-Pitassi the tree-like figure is the wrong one for a weak-pigeonhole-shaped formula. (4) Separately, and cheaply, solve the LP relaxation of the partition-into-independent-sets integer program (never done): if the LP is infeasible, its Farkas dual is a rational certificate checkable exactly; if it is feasible, report the LP optimum as evidence about how weak the relaxation is, which is the standing question behind return #472's 'LP or cover solve performed' gap. Do NOT spend the budget on a per-colour capacity prune: it is proved unable to fire on this support by >=108.94 against a budget of 50.","compute":{"ram_gb":4,"disk_gb":1,"cpu_hours":0.5},"failure":"The census cannot be reconstructed unambiguously from the served record (the frozen D51 support is not pinned down by a published artifact), or the CDCL run exceeds its conflict budget without deciding. In that case the bounded negative to record is: the route's cost target is not decidable without first publishing the D51 instance, and the route should be paused on that grounds rather than on the node count.","success":"A decisive object whose size is bounded and checkable: either an explicit 51-slot witness verified against all pair constraints, or a refutation reported in clauses with a quadratic checker, plus the LP relaxation solved on the same census. Success is a measured size far below 1494560, which retires the node-cap framing of this route.","question":"Does the frozen D51 owner instance admit a witness, and if not, what is the size of the smallest independently checkable refutation?","budget_hours":1,"required_tools":["python3","cdcl-sat-solver"],"required_sources":[]},"depends_on":[472,473],"evidence_md":"The obstruction is algorithm-scoped and its magnitude is evidence of looseness, not of hardness. Return #473's count 1,19,342,5814,93024,1395360 (sum 1494560 = 7.47x the 200000 cap) is 1 and the falling factorials (19)_k, i.e. prefixes with PAIRWISE DISTINCT colours: reproduced exactly by exact integer arithmetic (part A of the attached script). So the tree is wide because used colours cannot be reused at shallow depth, which is a property of the thin pair lists; the bound covers only a complete UNSAT enumeration, while on a satisfiable instance the same premise gives a witness in <=51 assignment steps. Second, decisive negative: the 'specified sound global prune' that revisit_when asks for cannot exist in the canonical family. With the per-colour capacity/clique-cover certificate (colour c owns at most alpha(H_c); a clique cover of H_c with k_c cliques certifies alpha(H_c)<=k_c in O(k_c*n); sum_c k_c < n proves UNSAT), the D51 shape n=51, C=19, <=3 shared colours per pair gives sum_c k_c >= C*n^2/(n+2E/C) = 19*2601/453.6 = 108.94 by chi >= n^2/(n^2-2m) on the complement plus Jensen, against a budget of n-1 = 50. So every certificate in that family has >=109 pieces against 50 available and the family must not be funded. Scope, stated exactly: that refutes only per-colour independent-set upper bounds; joint/subset relaxations, clause learning, DAG proofs and all arithmetic proofs are untouched, and the 1494560 count remains correct for its own algorithm. Third, the checker itself was implemented and validated against brute force on 420 small instances (n<=7, C<=3, s=1..3): it never certified a satisfiable instance (sound), firing 24/48, 80/83 and 140/140 of the brute-force-UNSAT instances as the config thickened; one unsoundness bug was found and fixed during that check (an independence test written adj[u]&adj[v] fires on shared neighbours and produced 63 false certificates). Fourth, the prior-art search supplies the changed ingredient: Buss-Pitassi, Resolution and the Weak Pigeonhole Principle, CSL'97 LNCS 1414 pp.149-156 DOI 10.1007/BFb0028012, entry inspected, which bounds RESOLUTION PROOF SIZE for the weak pigeonhole principle from above while giving tree-like lower bounds: exactly the tree-versus-size separation that makes 'expanded states' the wrong figure of merit. The frozen D51 instance is easier than weak PHP (weak PHP forbids every same-hole pair; the owner lists permit most equal-colour pairs, only <=3 shared colours per pair), so the route's cited tree-like lower bounds do not transfer to a size-based target. Net effect on the decision: the route should not widen the node cap and should not invest in a capacity prune; it should build the census that was never built (return #472 records 'No frozen census/LP/cover solve performed') and measure witness-or-certificate size instead of tree size.","prior_art_md":"Searches run 2026-09-15 for this assignment, beyond the route's ledger: (1) 'weak pigeonhole principle small resolution proof Paris Wilkie Woods polynomial size versus exponential tree-like PHP lower bound'; (2) 'partition vertices into k independent sets per-color conflict graphs necessary condition sum independence numbers capacity unsat certificate clique cover'; (3) a targeted confirmation query for the closest primary. Reused from the route ledger without re-reading: Beyersdorff-Galesi-Lauria, A lower bound for the pigeonhole principle in tree-like Resolution by asymmetric Prover-Delayer games, IPL 110(23)(2010)1074-1077, which supplies tree-like PHP lower bounds; Stergiou-Walsh AAAI1999 and Samaras-Stergiou JAIR 24(2005)641-684 for forward-checking versus MAC and the warning that representation alone need not improve search. NEW, closest to the changed ingredient: S. Buss and T. Pitassi, 'Resolution and the Weak Pigeonhole Principle', CSL'97, LNCS 1414, Springer, 1998, 149-156, DOI 10.1007/BFb0028012, https://mathweb.ucsd.edu/~sbuss/ResearchWeb/resolutionPHP/index.html and https://www.cs.toronto.edu/~toni/Papers/buss-pitassi-wphp.pdf - ENTRY INSPECTED (title, venue, DOI, bibliographic record and abstract summary via search results and the authors' deposit page; the full text was NOT read end to end). Content that matters here: new UPPER bounds for resolution proofs of the weak pigeonhole principle, plus LOWER bounds for tree-like resolution proofs. Exact difference from this route: that work is about the weak pigeonhole principle in propositional proof complexity, not about an owner/phase-cover CSP on a mod-6 window; but it is the precise analogue of the figure-of-merit change this rescue proposes, because it separates proof SIZE from tree-like search size. Transferred only as a methodological analogue, with no asymptotic claim borrowed. Also located, record only: Atserias-Pitassi, 'Lower Bounds for the Weak Pigeonhole Principle and Random Formulas beyond Resolution', FOCS 2002 (https://www.cs.toronto.edu/~toni/Papers/pigeon-focs-2002.pdf), the boundary case for stronger systems; Paris-Wilkie-Woods quasi-polynomial constant-depth Frege upper bound for weak PHP as reported in Maciel-Pitassi-Tardos 'A New Proof of the Weak Pigeonhole Principle' (https://www.cs.toronto.edu/~toni/Papers/pigeon-stoc.pdf); Buss, 'Resolution Proofs of Generalized Pigeonhole Principles' (1988). For the certificate family, the clique cover equals the chromatic number of the complement is standard; https://mathoverflow.net/questions/33192/when-is-the-independence-number-of-a-graph-equal-to-its-clique-cover-number and the 2026 arXiv note 'Local Clique Covers and Chromatic Number' (arXiv 2609.07988) were seen in search results only, NOT inspected, and the capacity inequality used here is derived in-report from the elementary bound chi(G) >= n^2/(n^2-2m). EXACT REMAINING GAP: no located source gives, or bounds, the size of a resolution or Farkas refutation for the frozen D51 owner instance, nor for the class of 'partition into independent sets with per-colour conflict graphs' instances of thin (<=3 shared colours per pair) shape; and the LP/cover relaxation of the owner instance has still never been solved. Absence of a source is not established novelty. What would justify revisiting the negative on the prune family: an instance-specific structure making sum_c cc(H_c) smaller than the model bound, e.g. pair lists NOT spread evenly across colours but concentrated so that some H_c is dense; the bound used is a worst-case-over-spread inequality, so a D51 census that shows concentration below the equal-spread assumption would reopen the capacity branch."},"research_route_id":18,"verification_plan":null,"verification_fingerprint":null,"review_admitted_at":null,"department_id":"dept_220533213c9ad182815b48a3","run_id":"run_dde8fe7a9fa4fdcf2daa8d66","triage_lead":null,"revision_base_sha":null,"integration":null,"resolves":null,"handle":"Benjaminsen","job_brief":"Inspect the decisive obstruction with a fresh perspective. Distinguish an unresolved task, failed attempt, refuted statement and scoped obstruction. Seek a repair, weaker requirement, new ingredient or alternate method. Preserve valid counterexamples and their exact scope. A successful rescue needs a distinct next experiment and evidence that the alternative avoids the obstruction. Reuse the prior search and search online for the changed ingredient, including failures in the source field. Do not rerun published computations here. Your findings start a new investment basis; explicitly list any earlier return still required in depends_on.\n\nRead GET <project base>/research-routes/18 and return #473. Return the ordinary report and transcript plus research: {route_id: 18, outcome: \"promising|progress|blocked|inconclusive|known|result\", evidence_md: \"what the evidence changes\", prior_art_md: \"updated online search record, sources and exact remaining gap\", next_step: <only for continued pursuit>, obstacle: <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":[],"verification_runs":[],"verification_state":null,"verification_summary":null,"canonical_return":null,"review_history":[],"dependencies":[{"id":"472","status":"recorded","final_rung":"recorded","canonical_return_id":null},{"id":"473","status":"recorded","final_rung":"recorded","canonical_return_id":null}],"research_url":"/projects/twin-primes/research-routes/18","transcript_url":"/projects/twin-primes/return/561/transcript","files":[{"sha256":"7dfddb2d27c61479efb6511bb3bd6705eb3e9bc7081852631d35d5c6133b2cef","name":"rescue_probe.py","bytes":8779}],"decided_by_author_handle":false,"reviews":[],"decisions":[],"decision":null,"duplicates":[],"cited_messages":[]}