Let β be the Beardwood–Halton–Hammersley constant: the shortest tour through n independent uniform random points in the unit square has length asymptotic to βn almost surely. Dong and Cao proved β≥0.6421 from an inequality β≥5/8+∑k=3KCk, where Ck is an integral over configurations of k points in the plane that form a connected graph when points at distance at most 1 are joined. For C3, C4 and C5, sharper bounds come from a first-order expansion of the area of the union of the unit disks on boxes of configurations. For C6+⋯+C22, which Dong and Cao did not use, a lower bound comes from comparing each point only with the three points before it in the order of their first coordinates. We obtain β≥0.6496, and β≥0.6508 if the exponential function of the C library used to evaluate the bound for C6+⋯+C22 has a relative error below 10−9. The proofs are computer-assisted; the bound 0.6496 is proved in Lean 4, with finite checks evaluated by compiled code, from the inequality of Dong and Cao and two statements about unions of disks that we prove but do not formalize.
Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23716094
A mix of human-written and AI-generated textHuman understanding: all parts
The Steiner ratio is the infimum, over finite sets of points in the Euclidean plane, of the length of a Steiner minimal tree divided by the length of a minimum spanning tree. Gilbert and Pollak conjectured in 1968 that it equals 3/2≈0.8660, and the conjecture is open. We prove that it is at least 2141/2500=0.8564, improving the bound 0.8559 of Ke, Huang, Shu, He, Gai and Wang. Their method reduces the induction step of Du and Hwang's 1983 proof of the bound 0.8 to finitely many inequalities on boxes in a space of local configurations of a Steiner minimal tree, which are checked by computer. These inequalities use estimates for the positions of terminals outside the local configuration. We prove all the geometric lemmas that our certificate uses, filling gaps in two proofs of Ke et al., and we add two such estimates that hold for more parameter values than the published ones. Within this method some new estimate is necessary: with the published estimates, no certificate of this kind reaches 0.856, whatever the boxes. The computer-assisted part is also verified in Lean 4, by a proof whose checks all run in Lean's kernel; the rest of the argument enters the formal proof as hypotheses.
Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23716009
A mix of human-written and AI-generated textHuman understanding: all parts
For more than fifty years, since Horowitz and Sahni's meet-in-the-middle algorithm of 1974, the best exponent for worst-case Subset Sum was 1/2. In October 2026 that barrier fell twice within a week, with OpenAI's 20.49n algorithm and, independently, Li and Ye's 2(1/2−1/450000)n≈20.4999978n, and improvements have followed quickly since: within three weeks A. Kapila's modification of the OpenAI approach ("Base") reached 0.4877, a retuning of Base by JoshuaQFEX reached 0.487676, and a refinement by Y. Bills reached 0.4876723. Here we push this line of work further and examine what limits it. Conditional on the cited non-numerical proofs, we give a certified parameter point with threshold T=0.4875754036: for every fixed T′>T, the uniform randomized algorithm uses O(2T′n) word operations on inputs of polynomial bit length, with success probability at least 2/3. In particular, it runs in time O(20.4875755n). A single asymmetric filter replaces Base's family of 43 filters. Independent interval computations certify all required numerical conditions, including both filtering moments and their quadrature errors.
We prove a lower bound on the first filtering moment, valid for all positive continuous densities, that excludes every parameter choice with τ≤0.484 in the original OpenAI proof's sufficient budget. Three algebraic bounds explain the costs at our improved point. Separately, an enumeration phase that inserts at least 2(1−η−o(1))n alias classes, spending a counted step on each, and uses checksum gap at most Δ needs exponent at least (1−Δ)/2. This is a conditional operation-count bound; a global upper bound on achievable checksum capacity remains open. Finally, we isolate a small-layer statement that would yield threshold 0.4873407528, prove combinatorial special cases, and identify the remaining questions.
Author comments: 30 pages, 2 figures. The main result is conditional on the written proofs of OpenAI (4 Oct 2026) and A. Kapila (commit 44c34961); its numerical conditions are certified in interval arithmetic. The companion file SECTION_T_v3.pdf (full proofs of the ternary alias step, Appendix A) is included with the source. Code, certificates, verification scripts and a timestamped research record: https://github.com/jv1000/subset-sum. AI use is described in Section 11.
A mix of human-written and AI-generated textHuman understanding: some partsAI-assisted mathematicsFourier filteringSubset Sumcomputer-assisted proofexact algorithmsinterval arithmeticmeet-in-the-middlerepresentation techniqueworst-case complexity
We ask for finite field versions of following three: (1) Grothendieck Inequality, (2) Johnson-Lindenstrauss Flattening Lemma, (3) Bourgain-Tzafriri Restricted Invertibility Theorem.
Contributed by Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář, Adrián Zámečník
In bottleneck multiple subset sum, items with weights are packed into knapsacks with capacities, possibly leaving items unpacked, so as to maximize the minimum load. For identical capacities the best possible approximation ratio is 2/3, and Chen et al.\ asked whether 2/3 is also achievable for arbitrary capacities. We show that it is not: for arbitrary capacities we give a 1/2-approximation using O(nlog(n+1)+mlog(m+1)) arithmetic and comparison operations for n items and m knapsacks, and prove that no fixed ratio above 1/2 is achievable unless P=NP. We also give a short proof of the classical 1/2 guarantee of Friesen and Langston for unit profits.
The Minimum Independent Dominating Set problem asks for a smallest maximal independent set of a graph. Unless P=NP it is not approximable within n1−ε for any ε>0; it is NP-complete on cubic planar bipartite graphs and NP-hard to approximate within δB on bipartite graphs of maximum degree B. We present version 0.0.9 of \textsc{Siriaisa}, an ensemble of eighteen strategies that adapts the vertex cover algorithm \textsc{Salvador} and the independent set algorithm \textsc{Esperanza} to independent domination: its exact subproblems are forests, solved by a conditioned tree dynamic program, in place of the bipartite structures of \textsc{Salvador}; one base strategy splits every vertex of degree larger than ⌊n⌋ into unconnected copies; and the improvers include a weighted swap search. We prove that the output is an independent dominating set computed in O(n+m) expected time, with ratio at most Δ, optimal on forests, and with ratio at most n on three classes of graphs. The degree-splitting strategy computes a dominating set of size at most ⌊n⌋(i(G)+s(G)) on every graph, for an explicit splitting excess s(G), and the output satisfies the same bound when the decoded set is independent. The excess is at most n(n+1), largest on complete graphs, zero for n≥D2 on every family of bounded degree D, among them the NP-hard and UG-hard bounded-degree families, and O(n) on planar graphs; on complete multipartite, crown, wheel and double-star graphs the output is optimal. We conjecture the ratio O(n) on all graphs; a proof would imply P=NP. In a reduction from satisfiability, every independent dominating set of the graph of a formula with N variables and t copies of every clause, t at least the largest clause width W, is a satisfying assignment, with N vertices, or has at least t+N vertices; with t=W, every independent dominating set of ratio smaller than 1+W/N is a satisfying assignment. This proves the n1−ε inapproximability directly from satisfiability, without a gap from the PCP theorem. Through a reduction of Chleb{\'\i}k and Chleb{\'\i}kov{\'a}, with an explicit edge gadget that turns a graph H into a graph h(H) with i(h(H))=τ(H)+2∣E(H)∣, where τ(H) is the minimum vertex cover size, every output on h(H) decodes into a vertex cover of H; we state the conditional consequences under the Unique Games Conjecture, for which a proof has been reported but not yet peer reviewed, on general graphs and, through the result of Austrin, Khot and Safra, on bounded-degree graphs. In reproducible experiments the output is optimal on 9999 of 10000 graphs with an exact integer-program optimum, on all 95 of 112 bipartite graphs whose optimum was proved, on all 18 instances of the set cover reduction, and on 2 of the 30 instances of the vertex cover reduction with a proved optimum; on ten Khot--Regev YES instances the decoded vertex cover has ratio between 1.25 and 1.8665. We also report the results on the 68 complements of the DIMACS clique benchmark.
Primarily AI-generated textHuman understanding: all partsApproximation AlgorithmBoolean satisfiabilityForest Dynamic ProgrammingMinimum Independent Dominating SetMinimum Maximal Independent SetP versus NPUnique Games Conjecturebipartite graphslocal search
The maximum independent set problem asks for the largest set of pairwise non-adjacent vertices in an undirected graph. It is NP-hard to approximate within n1−ε for every ε>0, and under the Unique Games Conjecture it is hard to approximate within O(Δ/log2Δ) on graphs of maximum degree Δ; the Khot--Regev form of the conjecture, for which a proof has been reported but not yet peer reviewed, also rules out a (2−ε)-approximation of Minimum Vertex Cover. We present version 0.1.6 of \textsc{Esperanza}, which takes the better of a dynamic minimum-degree (Caro--Wei) greedy set and the complement of the \textsc{Salvador} vertex cover, and improves it by three budgeted local searches: repair-and-grow restarts at the cover vertices and at a maximum-degree vertex, chained local restarts realising (k,k+1)-improvements, and an iterated (1,2)-swap search. We prove that it runs in O((n+m)αA(n)) expected time for fixed budgets, with αA the inverse Ackermann function. We prove that the output is a maximal independent set, that its complementary vertex cover has at most 2τ−r vertices, where τ is the minimum cover size and r the number of components with an edge, and that the ratio is at most (Δ+2)/3 on graphs of maximum degree Δ. We prove the ratio 2n on every graph with Δ≤n and on three further classes, and state it for all graphs as a conjecture, whose proof would imply P=NP. We also state the conjecture that the complementary cover has at most 2τ−∣M∣ vertices for the NetworkX minimum maximal matching M; a proof would give a 3/2-approximation for Minimum Vertex Cover and refute the Unique Games Conjecture unless P=NP. In reproducible experiments the returned set is optimal on all 30000 graphs of a suite certified by an exact integer program; on 40 Khot--Regev YES instances with 640 to 2560 vertices the conjectured bound is certified on 38 and open on 2; and on 31 bounded-degree graphs the certified ratio is at most 1.0769 on the families with a planted independent set.
Primarily AI-generated textHuman understanding: all partsApproximation AlgorithmBounded-degree GraphsLinear TimeMaximum Independent SetP versus NPUnique Games ConjectureVertex Coverlocal search
A completely multiplicative sign function is determined by its values on n2+1, n2+2, and n2−2, but exact determination does not quantify how many readings detect a negative prime sign. We distinguish three losses of information: partial compatibility tests, geometric restrictions on certificates, and fractional relaxation of signed constraints. After fixing a prime head, we describe the exact fibre of a window and the parity constraints joining two windows. For any fixed head and any sequence HN=No(1), one table with o(N) negative entries passes every HN-window test and every two-reading test. A separate finite table passes these tests without any global source. We bound certificate capacity - fractional packing under unit reading loads - for narrow and binary certificates and for low-degree transport libraries whose links cancel odd prime valuations in pairs. A fixed algebraic curve of certificates for a target prime p has at most logarithmic capacity, or capacity at most one when a reading is constant; in the infinite unanchored case its common poles have field Q(p). Conversely, selected values of n2+1 can force linearly many errors while the capacity of all certificates stays bounded. Two internally disjoint pair families compose without loss on their existing readings, whereas sixteen actual values exhibit Pack=3<Cap=4<μ=5. The selected-sample constructions do not give an upper bound for the minimum on a complete prefix.
We consider bin-packing instances with 3m items of sizes in (1/4,1/2), total size m, and configuration linear programming value m. Let d be the relative dimension of the polytope of zero-sum multiplicity patterns obtained by centering sizes at 1/3. We determine the maximum additive integrality gap for every d≤10. It is zero for d≤4 and one for 5≤d≤10. More generally, a representation of the multiplicity vector by at most five zero-sum patterns admits an integral packing, and a representation by at most eleven patterns requires at most one additional bin. The integral-packing result has a structural proof; the additive-one result combines structural restrictions with exact finite enumeration. For arbitrary d, we construct an LP-tight subinstance with at most 6d+3 items and no smaller additive gap. An integer representation preserving the signs of triple sums then yields a finite rational family attaining the worst gap, which is computable in time 2O((d+1)2). Finally, we construct a sharp family with simplex pattern polytopes and a linearly growing zero-sum matching deficit. Its eleven-dimensional member violates the zero-sum remainder condition used in the ten-dimensional proof. Thus the bound of eleven fractional patterns in that condition is sharp.
Primarily human-written textHuman understanding: all partsbin packingconfiguration linear programminghypergraph matchinglattice polytopeszero-sum patterns
Minimum Vertex Cover has a classical linear-time ratio of 2, and under the Unique Games Conjecture no polynomial-time algorithm achieves a fixed ratio below 2 unless P=NP. We present version 0.1.4 of \textsc{Salvador}, a linear-time ensemble of seventeen strategies, numbered in the order in which they are computed: twelve base strategies (component amplification before a maximal matching, the maximal matching itself, degree and weight heuristics, reductions to auxiliary problems that are solved exactly, a decomposition into bipartite layers, a weighted subdivision reduction and a bounded-treewidth dynamic program), followed by five improvers (a union pass, local search, reduce-and-search, consensus forcing and a swap-maximize refinement). We prove that every strategy runs in O((n+m)α(n)) time, and that the returned cover has at most 2τ−r vertices, where r is the number of components with an edge, so the ratio is at most 1.999999999 whenever τ≤109r. We prove exactness or a bounded ratio on several classes of graphs, among them every bipartite graph on which the Hopcroft--Karp phases of the layer strategy reach a maximum matching, and we give a per-instance certificate: a cover with at most 2L−∣M∣ vertices, for a lower bound L≤τ and the maximal matching M, is within ratio 3/2 on that instance. In a reproducible suite the returned cover satisfies ∣C∣≤2τ−∣M∣ on all 291 tested graphs with a known optimum and is certified on the six without one, although single strategies violate it; on the 68 DIMACS clique complements it is never worse than Hvala and optimal on 37 instances against 18. Whether ∣C∣≤2τ−∣M∣ holds on every graph is stated as a conjecture: a proof would give a linear-time 3/2-approximation and would refute the Unique Games Conjecture unless P=NP.
Primarily AI-generated textHuman understanding: all partsApproximation AlgorithmBipartite LayersEnsemble HeuristicsLinear TimeMaximal MatchingP versus NPSplit GraphUnique Games ConjectureVertex Cover
Contributed by Arthur, David Barros Hulak, Ruy J. G. B. de Queiroz
We explain a standalone Lean 4 and Mathlib verification of the finite counterexample announced by Dmitry Rybin to the cost-preserving single-source unsplittable-flow conjecture. The instance has seven vertices, nine directed arcs, and three terminal demands. An exact rational path flow saturates every arc, has cost 58, and has largest demand 15. Exhaustive graph-path classification reduces every unsplittable routing to two choices per terminal. Three backbone-arc inequalities force any routing with load at most the fractional load plus 15 to use at least two paid routes, each costing 30. Thus every such routing costs at least 60, ruling out cost preservation even with a non-strict congestion bound. We present the numerical certificate, its graph realization, and the boundary between the pinned proved implementation and its statement-only verification interface. The contribution is an exposition of a source-based formal certificate; no new counterexample, first formalization, or general rounding algorithm is claimed.