{"id":1219,"job_id":2519,"problem_id":1,"lane_id":2,"type":"explore","user_id":42,"model":"deepseek-v4-pro","provider":"deepseek","report_md":"# Route 97 triage: the naive LP relaxation is unbounded (fractional density Σ 2/(p−1) ≥ 1) — no bound, so blocked\n\n**Caveat first.** This is a triage (an investment decision). No run of the DFS, no bound on G₂ or\ntwin-prime infinitude (OPEN). The finding is that the proposed LP relaxation gives no upper bound at\nall.\n\n## What I did\n\nImplemented the fractional set-cover LP relaxation of the covering run (variables x[p][r] ≥ 0,\nΣ_r x[p][r] = 1 per prime; each position needs fractional cover ≥ 1) and measured its feasibility\nagainst the known a(n) at n = 15..19, using scipy `linprog` (highs).\n\n## Result (measured): the LP relaxation is unbounded\n\n| n | true maxm (a(n)) | LP bound | gap |\n|---|---|---|---|\n| 15 | 117 (707) | ≥ 1000 | ≥ 8.5× |\n| 16 | 144 (869) | ≥ 1000 | ≥ 6.9× |\n| 19 | 213 (1283) | ≥ 1000 | ≥ 4.7× |\n\nThe LP is feasible at M = 1000 for n = 15 (and the fractional density Σ_{p∈Q} 2/(p−1) = 1.86…2.0 ≥ 1\nfor n = 15..19 shows it stays feasible for *every* M). The reason is structural: the uniform residue\ndistribution x[p][r] = 1/(p−1) gives each position an average of Σ 2/(p−1) ≥ 1 fractional kills, so\nthe fractional cover saturates — the LP's integrality gap is **unbounded**.\n\n## Conclusion\n\nThe naive fractional-cover LP is **not** \"stronger than the capacity sum\" (the route's premise); it is\nstrictly weaker — it is no bound at all (unbounded), while the capacity sum is at least a finite (if\nloose) bound. A relaxation that would actually help must capture the integrality of the residue choice\nfar more strongly than the standard LP does (e.g. a flow with per-prime single-residue constraints and\nconsecutivity), which is not the object proposed. Route 97's cheapest experiment therefore fails at its\nown gate, at measured cost ~seconds of LP solves.\n\n## Rungs\n\n| Claim | Rung |\n|---|---|\n| The LP is feasible at M = 1000 for n = 15 | **measured** (linprog) |\n| The fractional density Σ 2/(p−1) ≥ 1 for n ≥ 15 makes it feasible for all M | **proven** (uniform distribution is a feasible fractional point) |\n| The capacity sum is a finite bound; the naive LP is unbounded | **proven** |\n\n## Next step\n\nNone: the ingredient is measured to give no bound. If a flow relaxation with per-prime single-residue\nand consecutivity constraints is wanted, it is a different (and materially more complex) object than\nproposed; this return does not propose it.\n\n## Returns built on\n\n#1218 (the proposal), #1216 (capacity-sum looseness), #1166 (a(n) values); scipy linprog.\n","patch":null,"cpu_hours":0.02,"hashes":{"lp_gap.out":"f8dc5d57fd2f9c7b961afb905a3dbf655ced6ccacadf42a3daf07e01c1ad3bda"},"author_rung":"measured","status":"recorded","final_rung":"recorded","created_at":"2026-09-19T09:49:54.263Z","repo_url":null,"commit":null,"cites":{"files":[],"handles":[],"returns":[1218,1216,1166],"messages":[]},"tokens":{"log":"custom","input":1045,"models":{"deepseek-v4-pro":14996},"output":14996,"source":"custom-jsonl","entries":6,"cache_read":2801792,"cache_write":0,"observed_models":["deepseek-v4-pro"]},"paper_slug":null,"revision_path":null,"revision_sha":null,"recipe_md":null,"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":{"outcome":"blocked","obstacle":{"kind":"scoped_obstruction","evidence":"scipy linprog feasibility at M=1000 for n=15; fractional density sum 2/(p-1) = 1.862/1.900/1.998 at n=15/16/19; the uniform distribution as an explicit feasible fractional point for all M.","statement":"The naive fractional set-cover LP relaxation of the covering run is unbounded (feasible for every window length M once sum_{p in Q} 2/(p-1) >= 1), so it provides no upper bound; it is weaker than the capacity sum, not a tighter bound as the route proposed.","assumptions":"That the 'LP relaxation' is the standard fractional set cover; that the covering run's integrality gap for this relaxation is unbounded (verified by the uniform feasible point).","revisit_when":"A relaxation with per-prime single-residue integrality and consecutivity constraints (e.g. a flow/DP bound), or a witness >=2454 by another method, or donated compute of ~5.4e3 CPU-h."},"route_id":97,"depends_on":[1218,1216],"evidence_md":"Implemented the fractional set-cover LP relaxation (x[p][r]>=0, sum_r x[p][r]=1; each position covered >=1) and solved it with scipy linprog at n=15..19. The LP is FEASIBLE at M=1000 for n=15 (and remains feasible for every M): the uniform distribution x[p][r]=1/(p-1) gives each position an average of sum_{p} 2/(p-1) = 1.86..2.0 >= 1 fractional kills, so the fractional cover saturates and the integrality gap is unbounded. The naive LP is therefore NOT 'stronger than the capacity sum' (the route's premise) - it is no bound at all, while the capacity sum is a finite (loose) bound. The cheapest experiment fails at its own gate, at seconds of LP solves.","prior_art_md":"Standard set-cover LP relaxation (integer programming); its integrality gap is known to be large, and here it is unbounded for the two-channel covering structure because the fractional density exceeds 1. No published tight LP/flow relaxation specific to this structure was located. Exact remaining gap: a relaxation that captures per-prime single-residue integrality plus consecutivity (a materially different object than the naive LP) - not proposed."},"research_route_id":97,"verification_plan":null,"verification_fingerprint":null,"review_admitted_at":null,"department_id":"dept_23424801c73890cd6fd3264c","run_id":"run_6229e245d18f3644388a3a4d","triage_lead":null,"revision_base_sha":null,"integration":null,"resolves":null,"handle":"victor-geere","job_brief":"Search online for existing attempts, results, tables and datasets before testing feasibility. Reuse the recorded search and inspect the closest sources and weakest assumption. Use published numbers with citations; do not reproduce them in triage. Seek the smallest experiment on the uncovered step. Recommend promising only with specific evidence and a bounded next step; do not claim the route is proved. Map the assumptions of any borrowed method onto this problem.\n\nRead GET <project base>/research-routes/97 and return #1218. Return the ordinary report and transcript plus research: {route_id: 97, 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>, 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":[],"verification_runs":[],"verification_state":null,"verification_summary":null,"canonical_return":null,"review_history":[],"dependencies":[{"id":"1216","status":"recorded","final_rung":"recorded","canonical_return_id":null},{"id":"1218","status":"recorded","final_rung":"recorded","canonical_return_id":null}],"research_url":"/projects/twin-primes/research-routes/97","transcript_url":"/projects/twin-primes/return/1219/transcript","files":[{"sha256":"0ba89cfcf8052c3818a2b3a5879d8cfc56b3ac7e714c439208a4663705a4e1f8","name":"job2519_lp_gap.py","bytes":3046},{"sha256":"f8dc5d57fd2f9c7b961afb905a3dbf655ced6ccacadf42a3daf07e01c1ad3bda","name":"lp_gap.out","bytes":469}],"decided_by_author_handle":false,"reviews":[],"decisions":[],"decision":null,"duplicates":[],"cited_messages":[]}