HEXAGONbeta

Subset Sum in time O(2^{0.4877n})

Primarily AI-generated textHuman understanding: some partscs.DS — Data Structures and Algorithmscs.CC — Computational Complexity

Contributed by Annanay Kapila ↗

Version 1 / Oct 15, 2026 / CC BY 4.0

Abstract

We present a uniform randomized classical algorithm for Subset Sum with running time O(2^{0.4877n}) in the word-RAM model, for inputs whose integer bit lengths are polynomially bounded in the number n of input integers. The algorithm halts on every execution and answers correctly with probability at least 2/3. The construction builds on OpenAI’s “Subset Sum in Time O(2^{0.49n})” (4 October 2026), retaining its framework of isolation, a capped preliminary search, a modular checksum, and alias subtraction. Two components are replaced: an alias procedure that computes phase sums using a smaller modulus, and a family of 43 checksum filters selected according to the input pattern. The analysis combines an averaged small-layer lemma, grouping by reduced and unreduced subset sums, and rigorous numerical certificates. Verification scripts using Arb ball arithmetic check the alias constraints and 430 moment inequalities. The argument relies on results from the earlier paper, which are restated in an appendix; the numerical certificates verify specified inequalities rather than formally verifying the entire proof.

Provenance statement

This manuscript was supplied by Annanay Kapila on 12 October 2026. It builds on OpenAI’s “Subset Sum in Time O(2^{0.49n})” and relies on results from that work. The manuscript reports numerical verification using Arb ball arithmetic through python-flint, with verification scripts included in Appendix D. The accompanying email reports that ChatGPT was used to review the manuscript. These numerical checks and the ChatGPT review do not constitute formal verification of the complete proof.

References

No bibliography entries or stable reference identifiers were extracted from this source.

Version history

  1. v1Submitted by Annanay KapilaInitial depositCurrentOct 15, 2026