Subset Sum: faster time and lower space

Source and verification

This article explains family 138 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Preliminaries: Subset Sum and exponential resources

Given positive integers $a_1,\dots ,a_n$ and a nonnegative target $t$, Subset Sum asks whether some index set $I\subseteq [n]$ satisfies

$$\sum _{i\in I}{a}_i=t.$$

Repeated values are allowed, and the empty subset solves the instance when $t=0$. The parameter $n$ counts input integers. Their maximum bit length, denoted by $b$, is a separate parameter.

The elementary meet-in-the-middle algorithm splits the indices in half. It lists each half’s subset sums and searches for complementary values $x+y=t$. This uses roughly $2^{n/2}$ time and stored entries, up to polynomial factors. Dynamic programming in the target costs roughly $nt$; since $t$ can be exponential in $b$, that is a pseudopolynomial bound.

Generating a list is different from storing it. Four smaller lists can produce sorted pair-sum streams without storing their complete Cartesian products, giving the classical half-exponential time and quarter-exponential space tradeoff. The family contains two manuscripts that improve different sides of this picture. The prerequisites are basic probability, modular arithmetic, Fourier sums on a finite cycle, and algorithmic time/space accounting.

🏷️ Two results in a specified word model

Both manuscripts use a uniform randomized classical word-RAM. The read-only input contains one integer per word. Word length is proportional to $n+b+\log (n+2)$. Arithmetic, division with nonzero divisor, bit operations, addressing, and fresh random words have explicitly charged unit costs within that width; larger arithmetic must be implemented with multiple operations.

Working space includes writable registers, tables, counters, retained random bits, and recursion state. There is no reusable uncharged random tape, advice, or externally supplied table.

Fix any positive integer $c$ and restrict asymptotic resource claims to inputs with $b\le n^c$. The algorithms are not given $c$ and do not depend on it. Resource constants and sufficiently-large-$n$ thresholds may depend on $c$.

Manuscript	Claimed resource bound	Correctness
Faster decision	Ordinary $O_c(2^{0.49n})$ time	Correct with probability at least $2/3$ on each input
Lower workspace	Polynomial times $2^{n/2}$ time; ordinary $O_c(2^{n/5})$ writable words	Never gives a false YES; finds a solution with probability at least $2/3$ on YES instances

The first assertion is from the October 4 manuscript. (OpenAI, 2026) The second is from its September 26 companion. (OpenAI, 2026a) Their resource caps hold on every random execution, including unsuccessful ones. They are separate algorithms; the family does not assert that one algorithm simultaneously achieves both displayed improvements.

The endpoint exponents require strict slack. The time construction first gives

$$K_0{2}^{0.489995n}(n+b+2{)}^K,$$

which is $O_c(2^{0.49n})$ when $b\le n^c$. The space construction gives

$$A_c(n+b+2{)}^{15}{2}^{0.199n}$$

writable words, which is $O_c(2^{\rho n})$ for every fixed $\rho >0.199$, including $\rho =1/5$. Neither absorption argument removes the polynomial factor at the smaller endpoint exponent itself.

🏷️ Faster decision through modular checksums

Reducing weights modulo a large integer $P$ creates false solutions: a subset can have the correct residue but the wrong integer sum. Call such a subset an alias. The time-improvement manuscript estimates a modular checksum and subtracts the aliases.

Let $e_P(u)=\exp (2\pi iu/P)$, and choose independent uniform phases ${\varphi }_i$ modulo $P$. For a subset $I$ put

$$\chi (I)=e_P\left(\sum _{i\in I}{\varphi }_i\right).$$

For transformed integer weights $c_i$ and target $t^{\prime }$, define $V$ by summing $\chi (I)$ over all subsets with sum congruent to $t^{\prime }$ modulo $P$. Subtracting the checksum of all aliases leaves exactly

$$B=\sum _{{\sum }_{i\in I}{c}_i=t^{\prime }}\chi (I).$$

On a NO instance this is zero. Random tie weights create polynomially many transformed targets such that, on a YES instance, with constant probability one target has a unique solution. For that target $|B|=1$, regardless of the phases. Thus an additive error below $1/4$ separates these cases with threshold $1/2$.

This is an isolation argument, not a claim that arbitrary sums of many unit complex numbers cannot cancel. The aliases and the modular checksum must also use the same retained phases. Resampling phases for subtraction would destroy the identity.

🏷️ Estimating the Fourier sum without enumerating it

Character orthogonality gives an exact formula. Writing $\rho =t^{\prime }\mathrm{mod}P$ and reducing $c_i$ modulo $P$,

$$\begin{array}{rl}{V}_{\rho }& =\frac{1}{P}\sum _{k=0}^{P-1}{J}_{\rho }(k),\\ J_{\rho }(k)& =e_P(-k\rho )A(k),\\ A(k)& =\prod _{i=1}^n(1+e_P(x_i(k))),\\ x_i(k)& ={\varphi }_i+k{c}_i(\mathrm{mod}P).\end{array}$$

Expanding the product creates one term per subset; averaging its character retains precisely those subsets with the desired residue. This proves the formula but is not yet a fast algorithm: $P$ is too large to scan all frequencies.

Naive uniform frequency sampling is also inadequate. For a fixed frequency, independence of the random phases gives $\mathbb{E}|J_{\rho }(k){|}^2=2^n$. The desired checksum accuracy is absolute and constant, so this second moment can be expensive.

The construction splits a frequency into high and low digits. Their separate coordinate vectors have a difference equal to the phase vector at that frequency. Random tables filter the high and low lists independently; matching accepted entries recover selected frequencies.

Coordinates are grouped into blocks of size about $\sqrt{n}$. A finite grid describes each block’s average filter scores, producing only $2^{O(\sqrt{n})}$ possible patterns. The algorithm enumerates these patterns, not every frequency. For each pattern, the filter parameters balance marginal list sizes against the probability that a pair survives together.

A frequency may appear in several table matches. Dividing its contribution by that multiplicity removes the resulting bias. Small collections of matches are enumerated; large ones are sampled using the appropriate weights. Moment estimates are taken under the original random-phase distribution. Conditioning on a successful filter event and then reusing unconditional independence would not justify the estimate.

The quantitative improvement depends on two circle-density inequalities and their finite implementations. The manuscript supplies rational numerical enclosures for these inequalities. These notes have not rerun that numerical certification; the constants are part of the attributed source result.

🏷️ Extracting aliases without a hidden enumeration cost

The checksum is useful only if all aliases can be recovered within the same time budget. The alias procedure exploits many representations of a subset as a pair of partial records. These records include both weights and masks specifying which shared indices they use. Disjointness of masks ensures that a pair represents a genuine subset rather than counting an index twice.

Random-prime filtering controls the number of pairs whose nonzero integer discrepancy is divisible by the prime. A crucial implementation order makes that argument applicable: remove all exact integer-match pairs before enumeration, including pairs with invalid overlapping masks. Every remaining discrepancy is then nonzero and admits a prime-divisor bound. Only after the bounded modular enumeration does the algorithm check mask compatibility.

If it first enumerated every modular match and discarded invalid exact matches afterward, the rejected pairs could already exceed the time budget. Correctness of the final retained set would not repair that resource failure.

The proof also separates instances with few distinct partial sums from those with enough distinct sums to supply many useful representations. This distinction concerns worst-case input structure; random phases do not assume that the input integers themselves are random.

Finally, finite-precision evaluation, bounded sampling, and operation counters turn the ideal checksum construction into an algorithm with a time cap on every run. A capped failure returns NO. Because incomplete alias extraction can affect a checksum, the stated fast algorithm has bounded two-sided error; it does not inherit the companion’s one-sided guarantee.

🏷️ Lower space through deficiency and representations

For a block $U$ of indices, let $N(U)$ be its number of distinct subset sums. Define the deficiency

$$d(U)=|U|-{\log }_{2}N(U).$$

If every subset has a different weight, deficiency is zero. If many subsets share weights, deficiency is large. For example, $m$ equal positive weights have only $m+1$ distinct subset sums, so their deficiency is $m-{\log }_2(m+1)$.

The space manuscript runs two trials each round. It does not compute which deficiency regime holds.

In the high-deficiency regime, seven disjoint blocks have short lists of distinct weights with suitable probability. Because the blocks are disjoint, their internal subset identities can be forgotten for decision purposes. Sorted pair-sum streams combine the lists. A random prime divides left combinations into buckets, and the algorithm stores one bucket at a time, skipping one that exceeds capacity. The success proof only needs the bucket containing a fixed solution to fit.

In the low-deficiency regime, many distinct sums support many decompositions of a fixed solution. A random sign transformation makes that solution uniformly distributed as a subset: negate weights on a random set $F$ and replace the target by $t-{\sum }_{i\in F}{a}_i$. The original solution $S$ becomes $S△F$. Distinct-sum counts are preserved, since the transformation is a bijection of subsets followed by a fixed translation of their sums.

Two parent records are each built from two children, which are themselves generated from stored leaf lists. Shared-index masks track compatibility at every join. Equal weights with different masks remain different records: their compatibility with the opposite parent may differ.

🏷️ Prefix refinement and honest regeneration costs

An extra independent prime subdivides parent records into buckets. Different weights are unlikely to collide, but equal weights always stay together. Thus another random modulus alone cannot resolve every large bucket.

The algorithm treats the two sides differently. It skips an overflowing left bucket. On the right, it fixes successive bits of the shared-index mask and regenerates the corresponding records. These prefix restrictions are imposed in the leaf lists before the joins.

Let $m$ be the number of shared mask bits, $C$ the dictionary capacity, $q$ the number of buckets, $J_L,J_R$ the numbers of raw tuple occurrences, and $U_L,U_R$ upper bounds on distinct valid records. Suppose a generation task with $Z$ potential occurrences costs at most $H+KZ$. The manuscript’s accounting lemma bounds the number of tasks by

$$T_{\mathrm{tasks}}\le 2q+2(m+1)U_R/C$$

and their total work by

$$\begin{array}{rl}{W}_{\mathrm{gen}}\le & H{T}_{\mathrm{tasks}}\\ & +K(J_L+(m+1)J_R).\end{array}$$

The reason is concrete. At a fixed prefix depth, right tasks describe disjoint sets of raw tuples. Each tuple has exactly one bucket and one prefix at that depth, including tuples eventually rejected for overlap. It is therefore charged at most once per depth. Distinct-record counts bound how many tasks can overflow; the term $H{T}_{\mathrm{tasks}}$ separately pays for repeated leaf generation and stream setup.

Counting only final dictionary entries would miss duplicate tuples and failed overlap tests. Counting only tuples would miss the repeated setup cost. Both terms are needed.

🏷️ Disjointness, success probabilities, and hard caps

The final test seeks parents $(x,D)$ and $(y,E)$ with $x+y=t^{\prime }$ and $D\cap E=\varnothing$. Random separating sets contain the left mask and avoid the right mask, reducing a surviving pair to an exact two-sum test. Splitting the shared block into four pieces and traversing the choices depth first keeps intermediate arrays small.

The success proof fixes a useful representation before exposing the extra prime and separating families. Representation survival may have only inverse-polynomial probability. Resource-failure probabilities must therefore be small enough to subtract before conditioning on that rare event; a generic high-probability bound without the needed scale would be insufficient.

Dictionary capacities enforce space on every execution. Bounded samplers and operation counters enforce time. Fresh independent rounds amplify success, while a YES answer always corresponds to an exact compatible subset. Old random values are reused only while stored in counted memory.

One-tape simulation also saves space by recomputation. The additional challenge here is to control the regenerated work tightly enough to retain the half-exponential time bound.

🏷️ Key steps and proof outlines

Multiplicity correction gives an exact checksum identity

Fix one frequency pattern $\pi$ in the faster-time construction. Its accepted high-digit and low-digit entries are grouped by their table-index tuple. If group $\nu$ has side lengths $a_{\nu },b_{\nu }$, the total number of matches is $L_{\pi }={\sum }_{\nu }{a}_{\nu }{b}_{\nu }$. Prefix sums of these products permit a uniform random match without enumerating all pairs: choose an integer below $L_{\pi }$, locate its group, and use quotient and remainder to choose its two entries.

A frequency $k$ has a unique digit decomposition but may be accepted by many table tuples. Its multiplicity ${\mu }_{\pi }(k)$ is the product, over coordinate blocks, of the numbers of block tables accepting both digits. The algorithm recomputes it using the same stored tables and deterministic score approximations used to generate the lists. Consequently multiplicity is an exact integer identity, even when the score approximations themselves are imperfect.

On the coverage event, every frequency assigned to this pattern occurs. A uniform match selects $k$ with probability ${\mu }_{\pi }(k)/L_{\pi }$. Give that match value

$$X_{\pi ,\rho }=\frac{L_{\pi }{J}_{\rho }(k)}{P{\mu }_{\pi }(k)},$$

or zero if it lies outside the frequency range or has another deterministic pattern. Its expectation is exactly the desired pattern contribution. For $N$ independent sampled matches, the conditional mean squared error is at most

$$\frac{L_{\pi }}{N{P}^2}\sum _{k:\mathrm{pattern}(k)=\pi }|J_{\rho }(k){|}^2.$$

Indeed, the exact second moment contains an additional factor $1/{\mu }_{\pi }(k)\le 1$, and independent centered complex errors have zero cross terms. This is the calculation in “Modular checksum estimator”; the filter estimates then control its right side. (OpenAI, 2026b)

Conditioning is postponed until the right inequality is available

The displayed variance calculation fixes phases and tables. It does not make the phases independent under the coverage event. The source first bounds the variance expression multiplied by the coverage indicator pointwise, and only then averages under the original phase law, where independence is valid. This order avoids a common conditioning error in randomized filtering.

The aliases must use exactly the same phases as the modular checksum. Subtracting their contributions is a deterministic cancellation identity once those phases are fixed. Isolation then creates, with constant probability, a transformed target with one true solution. Its remaining contribution has modulus one; the NO case has remaining value zero. A constant absolute approximation error separates those cases without needing any anti-cancellation theorem for multiple solutions.

The random-prime enumeration also requires a pointwise preliminary step. For a nonzero integer discrepancy $D$, only primes dividing $D$ can create a modular collision, and the number of such large prime divisors is bounded by the bit length of $D$ divided by the prime-size scale. This argument says nothing when $D=0$. The source therefore removes every exact-match pair before bounded modular enumeration, including pairs later rejected because their masks overlap. Resource control needs the discrepancy to be nonzero before paying enumeration cost.

Prefix splitting charges raw occurrences and setup separately

For the space companion, think of each generated parent as a raw tuple of leaf records. Several tuples can yield the same weight and mask; others fail compatibility. At any fixed mask-prefix depth, a tuple belongs to exactly one bucket and one prefix task. Hence right-side regeneration charges it at most once per depth, for at most $m+1$ depths. Left tuples are generated once. This yields the occurrence work $K(J_L+(m+1)J_R)$ from the earlier bound.

That does not pay for restarting a stream. Every task has an additional cost $H$ for leaf preparation and initial heap construction. A task that overflows capacity $C$ contains more than $C$ distinct valid records. Disjointness of tasks at each depth bounds the number of such nodes; binary splitting then bounds their children. The resulting task count is at most $2q+2(m+1)U_R/C$, and multiplying by $H$ pays the missing setup cost. Equal-weight records remain separable through their masks even when no modulus can separate their weights. (OpenAI, 2026a)

Finally, fix a useful representation before exposing the independent refinement prime and separating sets. If its survival event has probability $p$, subtract an unconditional resource-failure probability smaller than $p$ before conditioning on survival. An error bound that is merely small in an absolute sense could exceed an inverse-polynomial $p$. This probability ordering, hard dictionary capacities, and explicit operation caps together establish the companion’s per-execution resource guarantees and one-sided correctness; they are separate from the two-sided checksum algorithm’s guarantees.

🏷️ Manuscripts and verification scope

• Subset Sum in Time O(2^(0.49n)) — pinned manuscript and companion source.
• A Low-Space Algorithm for Worst-Case Subset Sum — pinned manuscript and companion source.

No family scope page was present at lean/docs/138.md in the pinned snapshot. This does not establish that all related formalization code is absent. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026a. A Low-Space Algorithm for Worst-Case Subset Sum.

🐻  OpenAI 2026b. Subset Sum in Time O(2^(0.49n)).