# Prior-art record, job #1288 (route 22, pursue), search date 2026-09-15 ## Reused, not repeated Route 22 revision 2 carries the triage search of return #560 (MathOverflow 67907 on the linearised Jacobsthal LP, computed to n = 75; Prékopa, *Boole–Bonferroni Inequalities and Linear Programming*, Oper. Res. 36(1):145–162, 1988, abstract only, full text paywalled; Polymath8b arXiv:1407.4897 §8 and Tao's 254A Notes 4 for the parity obstruction on *approximate* data). I did not repeat those queries. The gap that search left open was: no located source asks how the LP optimum grows with the truncation level D relative to the window length X when the modulus-level data is **exact** and anchored. ## Queries run 2026-09-15 for this assignment 1. `linear programming lower bound sieve exact counts truncation level D growth "level of distribution" certificate bounded parity obstruction LP optimum` 2. `Bonferroni inequality linear programming best lower bound union events restricted atoms "product of primes" sieve twin primes finite window exact counts` ## New sources located, and what they change - **Kaski, Mannila, Mohapatra, *Optimal Union Probability Interval Is NP-Hard*, arXiv:2605.03556** (submitted 2026-05-05, revised 2026-08-10; abstract page inspected, full text not read). Computing the optimal interval for a union probability from partial intersection information is NP-hard, framed explicitly through **Hailperin's linear program on the atoms of a Venn diagram** — the same object as route 22's LP over strike types. It resolves an open question of Pitowsky and Boros et al. *What it changes for this route:* the general problem's hardness is why an atom restriction matters at all, and it explains why the route's LP stays tractable only because the arithmetic rule `prod(T) ≤ X²` cuts 2^m atoms down to a polynomial set (measured below: 273035 atoms at p = 151 against 2^34 subsets). It does **not** bear on the arithmetic question. - **Yang, Alajaji, Takahara, *A Short Survey on Bounding the Union Probability using Partial Information*, arXiv:1710.07576** (2017-10-20; abstract page inspected). The survey is restricted to bounds from **individual or pairwise** event probabilities. Route 22's data is exact intersection counts for every prime set with `prod(R) ≤ D`, which is higher-order, so this line does not cover the question. Recorded to close it off rather than because it applies. - Also returned and not pursued: Prékopa's INFORMS record for the 1988 paper (still paywalled, so #560's access gap on it is unchanged), and *Lower Bounds for the Probability of a Union via Chordal Graphs* (arXiv:1004.3416), which exploits graph structure among events rather than a truncation level. ## The exact remaining gap after this assignment The question route 22 posed — whether the exact-count certificate at level `D = X` grows with p — is now **measured and answered negatively** (it decays and reaches 0 at p = 83; table in the report). No prior source was found that asked it, and none is needed to close it: the answer is a computation, and it is in this return. What the search did **not** cover, and what a successor would have to search before building on the contrast reported here (level `X` certifies 0 while level `X^1.25` still certifies ~80% of the zone twins): literature on the **threshold exponent** at which a finite exact-data sieve certificate collapses — I found nothing addressing it, and I did not search specifically for it, so that is an open gap rather than a novelty claim.