A self-contained proof of the exponent threshold 0.4875754036 for worst-case Subset Sum
Version 1 / Nov 18, 2026 / CC BY 4.0
Abstract
We give a complete written proof that Subset Sum on n positive integers of polynomial bit length is decided by a randomized word-RAM algorithm in time O(2^(T'n)) for every fixed T' > T = 0.4875754036, in particular in time O(2^(0.4875755n)). The threshold T was reported earlier by the author, conditionally on the non-numerical lemmas of two preprints; the contribution of this paper is the derivation that removes that condition. The algorithm is the one introduced by OpenAI (isolation, a capped preliminary search, a filtered modular checksum, subtraction of aliases) with the alias step of A. Kapila (one large shared block, sparse masks, alias phase sums) and a single asymmetric checksum filter. Those ideas are theirs. What is done here is different in kind: every non-numerical lemma that the result uses is stated with its hypotheses and proved in this text, so that the argument can be checked without accepting unproved statements from other preprints. The numerical inequalities that the proof uses are listed explicitly and matched one by one to a ball-arithmetic certificate, whose analytic error bounds are also proved here. The theorem has no mathematical hypothesis beyond two cited classical theorems and those certified inequalities. The manuscript also records, statement by statement, how each proof was obtained and which independent checks are still open. It has been reviewed and audited, with the sources open, by a second AI system; it has not been refereed.
Provenance statement
References
- OpenAI, Subset Sum in Time , manuscript with \ source, 4 October 2026. https://github.com/openai/math/tree/main/preprints/Subset-Sum-in-Time-2-power-0-49n-October-4-2026.link
- A. Kapila, Subset Sum in time : a complete proof , manuscript ( subset-sum/PROOF_0.4877.tex ), 14 October 2026. https://github.com/a-kapila/maths-proofs, commit 44c34961 .link
- J. Voitle, A certified exponent of for worst-case Subset Sum, and limits of the alias--checksum analysis , preprint, hexagon:2611.00178, November 2026.hexagon
- J. B. Rosser and L. Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J.\ Math. \ 6 (1962), 64--94.
- L. N. Trefethen and J. A. C. Weideman, The exponentially convergent trapezoidal rule, SIAM Review 56 (2014), 385--458.
- K. Mulmuley, U. V. Vazirani and V. V. Vazirani, Matching is as easy as matrix inversion, Combinatorica 7 (1987), 105--113.
- E. Horowitz and S. Sahni, Computing partitions with applications to the knapsack problem, J.\ ACM 21 (1974), 277--292.
- R. M. Karp, M. Luby and N. Madras, Monte-Carlo approximation algorithms for enumeration problems, J.\ Algorithms 10 (1989), 429--448.
- X. Chen, Y. Jin, T. Randolph and R. A. Servedio, Subset Sum in time $2^{n/2}/\poly(n)$, in APPROX/RANDOM 2023 ; arXiv:2301.07134.arXiv
- B. Li and L. Ye, Subset Sum via Partial Match , preprint, arXiv:2610.10446v2, 7 October 2026, revised 2 November 2026.arXiv
Show all 12 referencesShow fewer references
- J. Wharton, subset-sum-bound , manuscript and repository, 20 October 2026. https://github.com/JoshuaQFEX/subset-sum-bound, commit bed8e18 .link
- Y. Bills, subset-sum-conditional-refinement , manuscript and repository, v1.0.0, 21 October 2026, and v1.1.0 (verification supplement), 22 October 2026. https://github.com/yannouli/subset-sum-conditional-refinement, commit 590bb68 .link
Version history
- v1 · 49 pagesSubmitted by Jennifer Voitle49 pages. This paper removes the condition in the author's earlier preprint hexagon:2611.00178 ("A certified exponent of 0.48758 for worst-case Subset Sum, and limits of the alias-checksum analysis"), which stated the same threshold assuming lemmas of two other manuscripts. Certificate code and stored output: https://github.com/jv1000/subset-sum, folder selfcontained-2026 (MIT License).CurrentNov 17, 2026