Model and main result

We give a uniform algorithm with ordinary \(O(2^{n/5})\) working space under each fixed polynomial bound on the input-integer bit length. The distinction between ordinary and polynomial-suppressed space requires us to specify the model. Put \[\begin{gathered} b=\max\left(1,\left\lceil \log_2\bigl(1+\max(t,a_1,\ldots,a_n)\bigr)\right\rceil\right), \qquad u=n+b+2,\\ w=\left\lceil4\bigl(n+b+\log_2(n+2)\bigr)\right\rceil. \end{gathered}\] The input occupies read-only random-access memory, one integer per word. Unit-cost operations are word reads and writes, indirect addressing, comparisons, addition, subtraction, multiplication, integer quotient and remainder with nonzero divisor, bitwise Boolean operations, and shifts. Each operation has a constant number of \(w\)-bit inputs and outputs; arithmetic exceeding these limits must be implemented and charged as multiple operations. A fresh independent uniform \(w\)-bit random word costs one operation.

Every writable register, address, counter, stack, table, seed, and retained random value counts toward working space. Old randomness can be reused only if it remains in this counted storage. The only uncharged storage is the read-only input and the fixed finite program; there is no random oracle, advice, or externally supplied table depending on \(n\) or the input. All preprocessing, input accesses, table construction, and random sampling count toward running time. Space is the maximum number of writable words simultaneously in use.

Our polynomial-bit convention fixes a positive integer \(c\) and considers inputs with \(b\le n^c\). The algorithm is not given \(c\). Its asymptotic resource constants and threshold may depend on \(c\), whereas correctness is required on every individual input.

For fixed \(c\) and \(\rho>0.199\), the factor \((n+b+2)^{15}\) is absorbed by \(2^{(\rho-0.199)n}\). At the endpoint \(0.199\) the polynomial factor remains. The resource bounds apply simultaneously on each run, including unsuccessful runs. Randomness affects the probability of finding a solution; it does not permit the algorithm to exceed its time or memory budget.

Representations and their predecessors

A representation method gives a solution many decompositions, then keeps only decompositions satisfying selected congruences. The multiplicity creates room to filter the search without losing every copy of the solution. Howgrave-Graham and Joux [7] used this idea, including recursive representations and modular filtering, for random hard-knapsack instances. Dinur, Dunkelman, Keller, and Shamir [5] developed recursive dissection tradeoffs for knapsack under randomness assumptions. Austrin, Kaski, Koivisto, and Määttä [1] adapted that dissection framework to worst-case Subset Sum using randomized modular reductions and explicit resource controls.

For the present argument, the number of distinct partial sums matters as much as the number of decompositions. The residue-coverage argument of Austrin, Kaski, Koivisto, and Nederlof [2], extended to product moduli by Nederlof and Węgrzycki [9], turns many distinct weights into many occupied residue classes. Nederlof and Węgrzycki also combined multilevel representations with weighted disjointness tests. Their construction uses separating sets that contain one choice and avoid the other, building on the separating collections of Fomin, Lokshtanov, Panolan, and Saurabh [6]. We use the additional-prime filtering of Belova et al. [3], together with their separator cost estimate for the required range of mask sizes [3]. The proofs below supply the modified enumeration, probability, and workspace arguments needed for our construction.

Two trials and the proof strategy

For a set \(V\) of input indices, let \(N(V)\) be the number of distinct subset sums on \(V\), and define its deficiency by \[d(V)=|V|-\log_2N(V).\] A block of large deficiency has a short list of distinct weights; a block of small deficiency supplies many distinct choices for a representation. We analyze two trials according to the mean deficiency of a uniformly chosen block of a fixed size. The algorithm does not compute that mean: each round runs both trials with fresh randomness.

How many distinct sums does a block have?

For a domain \(V\subseteq\{1,\ldots,n\}\), let \(N(V)\) count the distinct integer values of its subset sums, and define \[\mathrm{d}(V)=|V|-\log N(V).\] We call this its deficiency. In particular, \(N(\varnothing)=1\) and \(\mathrm{d}(\varnothing)=0\). Here an actual weight is an integer sum, as opposed to a residue; masks always encode sets of indices, even when some input values agree. The next lemma applies also to signed weights, which arise later after a sign transformation.

Consequently, for any fixed \(\epsilon>0\), a deviation of \(\epsilon n\) from the size-specific mean has probability \(O(1/n)\), by Chebyshev’s inequality. This concentration concerns a random domain in a fixed input; it assumes no distribution of the numerical input values.

Exact entropy estimates

Cardinality restrictions on a block reduce its subset count from \(2^v\) to a binomial coefficient. We will need the exact exponential rate, including in a later estimate with no exponential slack.

Random primes and the sampling interface

The modular filters must control collisions of actual weights, even when their bit length grows polynomially with \(n\). We use the following elementary estimate with its full bit-length dependence.

We analyze uniform independent draws, conditional on each specified finite range. The implementation uses at most \(n^3\) attempts for each draw and fails the current trial if they all fail. The precise interface, proved in Lemma 14, is as follows. A draw from \(\{0,\ldots,D-1\}\) has the uniform law on success and couples to an ideal draw with failure probability at most \(2^{-n^3}\); \(D=1\) needs no randomness. A draw from \(\mathcal P_\ell\) has its uniform law on success and coupling failure at most \(e^{-n^2/4}\). These conditional bounds remain valid for ranges determined by past choices. All requested prime parameters satisfy \(\ell\le.258n\); bounded trial division therefore costs at most \(\operatorname{poly}(n)2^{.129n}\) per prime search, including all its attempts. The final section proves the finite-word implementation and the aggregate coupling estimate. The trials below use no unbounded sampling operation in their resource guarantees.

Sorted modular pair streams

A stream will enumerate a Cartesian product while retaining only its smaller input arrays. An item consists of its actual, possibly signed, weight and a constant number of index masks. Write \(\omega(a)\) for the actual integer weight of an item \(a\). Repeated occurrences remain separate even if all their fields agree. Each item occupies constantly many words; array indices have \(O(n)\) bits. We assume that weights, moduli, keys, and indices fit in the stated constant-word representation. Section 7 verifies these conditions for all uses below.

This is the sorted pair-sum method associated with Schroeppel and Shamir [10]; see also the explicit four-list description in Nederlof and Węgrzycki [9]. We give the modular ordering and stopped-execution argument locally, since those details determine the cost of regenerating a dictionary. A generator’s mutable state identifies its next occurrence and can be copied while sharing its immutable input arrays.

An actual-weight stream needs no modular pivots. Sort the second array by actual weight, add each first-array weight to that sorted row, and heap-merge the rows. Reading this ordered stream while remembering only the last weight counts its distinct values without storing the Cartesian product. This will let the representation trial measure a block’s deficiency exactly from two small half-block lists.

Bounded dictionaries

Streaming saves space only if we also control what is retained. For deterministic deduplication, use a binary trie on a fixed-width signed actual weight, followed by the relevant mask bits when a mask is part of the key. Give zero its canonical nonnegative sign. In our applications the complete key has \(O(u)\) bits. Searching or inserting it takes \(O(u)\) operations and introduces at most \(O(u)\) nodes, with constantly many words per node.

Keep a separate append-only array of the distinct entries if subsequent array access is needed. A duplicate changes neither the array length nor its mathematical content. On finding a new key that would increase the array beyond capacity \(C\), report overflow. Even if nodes for this first rejected key have been allocated, the trie has at most \(O(u(C+1))\) nodes. All nodes, addresses, and appended records count as workspace. A weight-only dictionary is appropriate for disjoint compression blocks; a weight–mask dictionary will be required when compatibility depends on shared indices.

For the concrete implementations below, raw list generation can be done in \(O(n^2)\) operations per item, sorting and heap work in \(O(n)\) per item or advance, and dictionary operations in \(O(u)\) per key. Whenever the combined stream storage is \(O(B)\), the term depending on \(Z\) in (5) is \(O(nZ)\), before the separately charged processing of those matches. The buffer and stream-length terms remain separate. These explicit degrees will be used when the task costs are bounded. The argument does not assign a cost merely from the number of distinct entries eventually retained.

Seven compacted blocks and four groups

Take the first \(7s\) indices of a uniform random permutation and divide them into seven consecutive blocks \(K_1,\ldots,K_7\) of size \(s\). For each \(i\), enumerate and sort all its subset sums, then compact repeated weights into a list \(D_i\) of distinct actual weights. Continue only if every list has at most \(2^a\) entries, where \[ a=\lfloor s-.0075n\rfloor. \tag{6}\] This preliminary enumeration stores at most \(2^s\) weights at a time. The seven retained lists are stored separately.

Of the remaining indices, give \[r_R=\lfloor .05n\rfloor \quad\text{to the right and}\quad r_L=n-7s-r_R \quad\text{to the left}.\] Choose these domains in their permutation order. Split the right raw domain into \(V_{R1},V_{R2}\) of sizes \(r_{R1},r_{R2}\) differing by at most one, and call the left raw domain \(V_L\). All these sizes are nonnegative on sufficiently large main-branch inputs.

For a domain \(V\), write \(\mathcal S(V)\) for its full list of indexed subset-sum occurrences, retaining repetitions. For two lists \(A,D\) write \(A\oplus D\) for the list with one occurrence of weight \(x+y\) for each pair \((x,y)\in A\times D\). Table 1 specifies the four generated groups by their two stored lists. A group stream enumerates the pair sums of the two lists in its row. The eight stored lists use separate subdomains, and the four group domains partition the input indices.

Sample \(q\) uniformly from \(\mathcal P_\ell\) with \(\ell=\lfloor .249n\rfloor\). For each integer \(z\in\{0,\ldots,q-1\}\), proceed as follows.

1. Generate \(\mathcal L_1\) by its direct key modulo \(q\) and \(\mathcal L_2\) by its complementary key \(z-\text{weight}\) modulo \(q\). Join equal keys using Lemma 6, with \(p=1\) and \(P=q\). Insert each resulting actual total weight into a weight-only dictionary of capacity \(C\).

2. If this dictionary overflows, discard it and move to the next \(z\). Otherwise retain its completed list of distinct weights. An empty completed dictionary may also be skipped.

3. Generate and join \(\mathcal R_1,\mathcal R_2\) in the same way, with target residue \(t-z\pmod q\). For every resulting actual right weight \(y\), search for \(t-y\) in the left dictionary. A hit returns YES. Otherwise free the dictionary and continue the residue loop.

A sampling failure also fails the trial. The bounded samplers and operation counter are those of Section 7.

Every retained block weight has a subset witness in its block. The four group domains are disjoint, so any choices witnessing an exact left–right weight match combine into an indexed subset of weight \(t\). Thus the trial has one-sided correctness. It need not retain witnesses or output them: its required output is the decision YES.

Work, space, and success

Let \(\mu\) be the mean of \(\mathrm{d}(V)\) when \(V\) is uniform among the size-\(s\) domains of the given input. The algorithm never computes this mean. It runs this trial and the representation trial in the same round; the following hypothesis identifies the case in which this first trial supplies success.

Compression has now handled the case in which random blocks have few distinct sums. When \(\mu<.00765n\), the next trial instead uses the many distinct sums to preserve a representation of a fixed solution through several modular filters.

Shared mixers and leaf lists

This trial gives each parent two children and each child two leaves. The leaves are stored; children and parents are generated from them. We first describe their index domains and prescribed cardinalities, then balance the unconstrained background parts so that every leaf is small enough to store. The shared blocks, which we call mixers, create multiple ways to represent a solution and require explicit disjointness tests.

Select three disjoint size-\(m\) sets uniformly from a random permutation. For each, compute its number of distinct actual subset sums exactly: store the subset-sum lists of two size-\(s\) halves and count distinct weights in their actual-weight sorted pair stream. Name a mixer with the largest such number \(M_0\), and name the other two \(M_L,M_R\) in a deterministic order, breaking ties deterministically. Put \[N_i=N(M_i),\qquad d_i=\mathrm{d}(M_i),\qquad i\in\{0,L,R\}.\] Continue only if \[ \max_iN_i\le (\min_iN_i)2^{\lfloor .0005n\rfloor}. \tag{11}\] Thus \(d_0\le d_L,d_R\) and the deficiency spread is at most \(.0005n\).

Choose a uniform subset \(F\) of all input indices, negate its weights, and replace the target by \[ t'=t-\sum_{f\in F}a_f, \tag{12}\] where the sum uses the original weights. In the rest of this trial all weights are signed after this change. The signed weight of any subset \(I'\) is the original weight of \(I'\mathbin{\triangle}F\) minus the original weight of \(F\). Thus the transformed instance is equivalent to the original, and Lemma 3 makes all \(N_i,d_i\) unchanged.

Independently guess \(k_i\) uniformly from \(\{\lceil m/6\rceil,\ldots,m/4\}\), for \(i=0,L,R\), and put \(\lambda_i=k_i/m\). At the top join, the left and right masks on \(M_0\) will have sizes \(k_0\) and \(s-k_0\). Within parent \(j\in\{L,R\}\), its two children will have masks on \(M_j\) of sizes \(k_j\) and \(s-k_j\). Disjointness of these masks is checked at the corresponding join. The left parent never uses \(M_R\), and the right parent never uses \(M_L\).

Independently choose a uniform labeled partition \[M_0=T_1\mathbin{\dot\cup}T_2\mathbin{\dot\cup}T_3\mathbin{\dot\cup}T_4, \qquad |T_a|=g.\] Choose integers \(c_1,\ldots,c_4\) as equally as possible with sum \(k_0\), assigning the remainder in a fixed order. The left count in \(T_a\) is \(c_a\) and the right count is \(g/2-c_a\). In each parent, child 1 uses \(T_1,T_2\) and child 2 uses \(T_3,T_4\), one block in each of its two leaves. In particular, within a parent the top-mixer indices in its children are disjoint.

Independently for \(j=L,R\), partition \(M_j\) uniformly into two labeled blocks \(Q_{j1},Q_{j2}\) of size \(s\). Prescribe child-1 counts \(a_{j1},a_{j2}\) as equally as possible with sum \(k_j\). The corresponding child-2 counts are \(s/2-a_{j1},s/2-a_{j2}\). Both children use the same two blocks of \(M_j\), one in each leaf; their possible overlap is exactly what the join of the two children into their parent checks. Figure 1 shows both parents and all eight leaves. Each leaf also receives its own disjoint background part, defined next. A chosen subset of a top block is recorded in the \(M_0\) mask, and a chosen subset of a local block is recorded in the \(M_j\) mask.

Nested modular filters

The first filtering level constrains each child’s weight; the second constrains the sum of the two children. Their moduli are nested so that once a parent and its first child pass, the required congruence for its second child follows. An additional independent prime \(q\) subdivides the parent residue classes into buckets, following the additional-prime filtering approach of Belova, Chukhin, Kulikov, and Mihajlin [3]. The low filters reduce raw generation; the extra prime controls the distinct entries in the solution’s bucket.

For analysis define the real quantities \[ \begin{gathered} \tau=.0078n,\qquad f_i=\min(\tau,d_i/2),\qquad L_i=s-f_i,\\ f_{\max}=\max_i f_i,\qquad \xi=n/4+.032m-f_{\max}. \end{gathered} \tag{16}\] The program uses the integer parameters \[\ell_i=\lfloor L_i\rfloor =\max\left\{\lfloor s-\tau\rfloor, \left\lfloor\frac{\log N_i}{2}\right\rfloor\right\},\] computed by bit lengths; flooring \(\log N_i\) first gives the same second term. Since \(d_0\) is smallest, \(L_0\) is largest. Sort the three \(\ell_i\) in nondecreasing order. For each increment from the preceding value, taking the initial preceding value to be zero, independently sample a prime with that increment as parameter if the increment is at least four; otherwise use the factor one. At each sorted index let \(p_i\) be the cumulative product. Tied parameters give the same product. In particular, \[p_L\mid p_0,\qquad p_R\mid p_0.\]

For every fixed nonzero relevant actual-weight difference \(\Delta\), conditional on these log parameters, the construction satisfies \[ \frac{2^{L_i}}{u^5}\le p_i\le 2^{L_i}, \qquad \Pr[p_i\mid\Delta]\le u^{10}2^{-L_i} \quad (i=0,L,R). \tag{17}\] For the size estimate there are at most three sampled factors; the discarded increments total at most nine. The prime lower ranges and the floor therefore lose a factor of at most \(2^{10}(4n)^3\) relative to \(2^{L_i}\), which is at most \(u^5\) for large \(n\). For divisibility, \(\Delta\) has at most \(2u\) distinct prime divisors. A factor with parameter \(\ell\) divides it with probability at most \(8u^2 2^{-\ell}\), by Lemma 5. All sampled factors are independent. Divisibility by their product requires divisibility by each sampled factor, so multiplication of these bounds, with the same discarded-increment and floor losses, proves (17). This argument does not require the sampled primes to be distinct.

Independently sample one more prime \(q\), with parameter \[\ell_q=\left\lfloor n/4+.032m-s+\min_i\ell_i\right\rfloor.\] Then \(\xi-2<\ell_q\le \xi\) and \(\xi\le .25768n\); in particular \(\ell_q\) is positive and linear in \(n\). The same prime estimates give \[ 2^\xi/u^2\le q\le 2^\xi, \qquad \Pr[q\mid\Delta]\le u^3 2^{-\xi} \tag{18}\] for each fixed nonzero relevant difference. Write \(P=p_0q\). Choose independent uniform residues \(\rho_0\pmod {p_0}\) and \(\rho_j\pmod {p_j}\) for \(j=L,R\), independently also of \(q\). Their desired parent low bases are \[w_L=\rho_0,\qquad w_R=t'-\rho_0.\] For side \(j\), require child 1 to have weight \(\rho_j\pmod {p_j}\) and child 2 to have weight \(w_j-\rho_j\pmod {p_j}\). The independent draw of \(q\) may be deferred until after all these choices when analyzing them.

Parent dictionaries and prefix recomputation

A parent dictionary stores records \((x,D)\): the exact signed integer weight \(x\) and the indexed top mask \(D\subseteq M_0\). Its key is both fields, so equal weights alone do not cause deduplication. A parent task consists of a side, a target residue modulo \(P\), and a possibly empty prefix of the \(M_0\) mask in a fixed index order. Left tasks use the empty prefix; right tasks may use a longer prefix. The task regenerates its four leaves, joins its two child streams, and either completes its dictionary or reports overflow.

The final check, specified in Lemma 10, tests whether two parent arrays contain disjoint top masks whose actual weights add to \(t'\). Its four random separating families are sampled once before the following loop, with the distribution specified in Section 5. Conditional on the layout, they use fresh randomness independent of every parent-generation choice, including the moduli, low residues, and extra prime, and are reused for all checks. Their values do not affect which parent tasks are generated or how those tasks process entries; a check can only stop the trial with YES.

For \(z=0,\ldots,q-1\), set \[v_L=\rho_0+p_0z, \qquad v_R=(t'-v_L)\bmod P,\] with normalized residues. On each side these range exactly once over the \(P\)-classes with the required parent low base. Since \(p_j\mid p_0\), the child low requirements do not change with \(z\).

First perform the left task. Its two child streams are obtained from their leaf pairs by Lemma 6, with modulus \(P\) and low modulus \(p_L\). Stream the first child by its weight modulo \(P\), and the second by \(v_L\) minus its weight modulo \(P\). Join equal keys. For each matched pair, check that its two \(M_L\) masks are disjoint. If so, retain just the actual total weight and the combined \(M_0\) mask, deduplicating these pairs in a dictionary of capacity \(C\). If a new distinct pair would overflow the dictionary, abandon this \(z\). Also skip \(z\) if the completed dictionary is empty.

Otherwise retain the completed left array and perform the analogous right task with residue \(v_R\), initially without an additional top-mask restriction. If its completed dictionary has between one and \(C\) distinct entries, apply the final check to that right array and the stored left array. If it is empty, do nothing. If it overflows, discard the task’s workspace and replace the task by two right tasks that fix the next bit of its \(M_0\) mask to zero and one, respectively. Process these tasks depth first, in a fixed order of the top-mixer bits. An overflowing task whose prefix already specifies the entire mask is simply dropped. Reuse or free the workspace after completing or discarding each task, and stop at the first YES.

In every prefix task, remove incompatible items from each leaf array before generating its streams. Test in that leaf exactly the prescribed prefix bits belonging to its own top block. Regenerating and filtering its raw leaf list from scratch is permitted. As each top block occurs in exactly one leaf of a parent, no raw four-leaf tuple with an incompatible top mask is generated in that task. This remains true even for tuples rejected later because their local-mixer masks overlap. It is this early restriction that permits the later charging of repeated four-leaf tuple processing by depth rather than by number of tasks.

Three bounds for prefix recomputation

The schedule has two different sources of work. Starting a task regenerates leaves and initializes streams; processing its matches examines raw four-leaf occurrences. A small dictionary can have many raw representations, including invalid local overlaps. We therefore use distinct entries to count task starts and raw occurrences to count match processing. A third count measures how often retained arrays are passed to the final check.

Inputs and sampled families

Recall the parameters \(u,m,g,C\) from (1). The four blocks in the representation layout give the partition \[M_0=T_1\sqcup T_2\sqcup T_3\sqcup T_4,\qquad |T_i|=g.\] Write \(k=k_0/m\in[1/6,1/4]\), where \(k_0\) is the prescribed left mask size. To recall the balanced block counts explicitly, write \(k_0=4d+r\) with \(0\le r<4\) and put \(c_i=d+1\) for \(i\le r\) and \(c_i=d\) otherwise. Then \(\sum_i c_i=k_0\) and \(|c_i-kg|<1\). The left array \(\mathcal L\) and right array \(\mathcal R\) are nonempty and have lengths at most \(C\). Their records are \((x,D)\) and \((y,E)\), respectively, with \(D,E\subseteq M_0\) and \[ |D\cap T_i|=c_i,\qquad |E\cap T_i|=g/2-c_i \quad(1\le i\le4). \tag{23}\] These conditions do not assert that an arbitrary pair is disjoint. For the transformed target \(t'\), the required output is YES only if some pair satisfies \[ D\cap E=\varnothing,\qquad x+y=t'. \tag{24}\] Array lengths count occurrences; distinct records are not required.

The actual weights and target have magnitude below \(2^{b+\lceil\log(n+2)\rceil+4}\). The exact arithmetic, masks, and array indices used here fit in a constant number of the words specified in Section 1; all stored tables and retained random choices count as workspace. The space bound for this check will hold on every outcome of the randomness.

Let \[\alpha=\log 3,\qquad \alpha_m=\frac{\lfloor\log(3^m)\rfloor}{m},\qquad e=\left\lfloor g\left(\frac12+ \alpha_m\left(k-\frac14\right)\right)\right\rfloor.\] The logarithm floor in \(\alpha_m\) is the bit length of the integer \(3^m\) minus one; no real-number oracle is needed. For each block set \[ \nu_i=\left\lceil 10\binom{g}{e}\bigg/\binom{g/2}{e-c_i} \right\rceil, \qquad \mathcal F_i=(S_{i,1},\ldots,S_{i,\nu_i}). \tag{25}\] All \(S_{i,j}\) are independent, and \(S_{i,j}\) is a uniform \(e\)-element subset of \(T_i\). The families are indexed: equal sampled sets retain their separate indices. The arrays and target are fixed independently of all four families.

The binomial arguments in (25) are feasible for large \(n\). To see this, put \[\zeta=\frac12+\alpha\left(k-\frac14\right),\qquad Y=\zeta-k=\frac14+(\alpha-1)\left(k-\frac14\right).\] Then \(e=\zeta g+O(1)\) and \(c_i=kg+O(1)\), uniformly in \(k\in[1/6,1/4]\). Since \(1<\alpha<2\), \(Y\) stays strictly between \(0\) and \(1/2\) throughout this interval.

As in Lemma 4, \(h\) denotes binary entropy and \(h_*=h(1/4)\).

Reusing the same families

The check can be called repeatedly with the same four families. Different calls are then correlated, but their work still adds by linearity of expectation. The necessary condition is that the full list of their input arrays be fixed independently of those families.

In the Subset Sum application, continue parent generation as if checks never returned YES and as if no operation cap were present, retaining all dictionary overflow rules. This defines the complete check list without consulting the separating families. Conditional on the layout, their sampled product law is independent of all parent-generation choices. It therefore remains unchanged after fixing that list and a designated check and witness selected from it using only those choices. Corollary 11 applies once Section 6.2 bounds the total input length of this list. The actual run visits only an initial portion of its work; the list itself is never stored, and coverage is required only for the selected pair.

Fixing a witness before the last random choices

Throughout this section suppose that the input is a YES instance and \(\mu<.00765n\), where \(\mu\) is the mean deficiency of a uniform size-\(s\) subset of the input indices. We first use ideal exact sampling. The extra prime \(q\) and the separating families are not exposed in this subsection. Our objective is to select one representation before either of those sources of randomness is used. We first balance the fixed solution inside the mixers, retain many distinct choices with the prescribed leaf counts, and finally show that the low residues hit some of them. Every selection of a witness in this argument is an analysis choice; the program enumerates candidates without knowing it.

Unconditional resource bounds

A surviving representation must reach a completed check before the operation cap. Recall the three ambient counts from the prefix analysis: \(G\) counts low-filtered raw child pairs, \(J_j\) counts low-filtered raw four-leaf tuples on side \(j\), and \(U_j\) counts distinct valid weight–top-mask entries passing only the parent low filter. None uses \(q\), a prefix restriction, or a separating family. The first two retain all occurrence multiplicities, including tuples with a local overlap. The last counts only valid entries and ignores the child filters. We shall bound these counts without conditioning on the rare survival event.

For their first moments, condition on a passing mixer setup, signs, guesses, layout and allowed moduli \(p_i\), leaving the low residues \(\rho_0,\rho_L,\rho_R\) independent and uniform. Each child’s required residue is marginally uniform modulo \(p_j\), including child 2 because \(\rho_j\) is independent of \(\rho_0\). Each fixed four-leaf tuple passes its parent filter and first-child filter with probability \(1/(p_0p_j)\); divisibility \(p_j\mid p_0\) then gives the second-child filter. Before its parent filter, the number of distinct valid entries on side \(j\) is at most \[2^{r_j}\,2^{H_{0j}m}\,2^{m-d_j}.\] Here the three factors count background choices, possible top masks, and distinct actual weights from disjoint use of \(M_j\). The last factor is \(N_j\), also for the signed weights. Each entry passes the parent filter with probability \(1/p_0\).

Define the analysis scales \[ \begin{aligned} \Gamma&=\frac n4+\left(-\frac54+\frac32h_*\right)m+f_{\max},\\ d_*&=\min(d_L,d_R),\\ \Lambda&=\frac n2+(\overline H_0-1)m-d_*+f_0. \end{aligned} \tag{34}\] By (13), (14), and (17), the conditional moments satisfy \[ \mathbb EG\le u^{26}2^\Gamma,\qquad \mathbb E(J_L+J_R)\le u^{51}2^{n/2},\qquad \mathbb EU_j\le u^{10}2^\Lambda. \tag{35}\] For the first bound, use \(\beta_j-L_j\le\Gamma\), the \(u^{20}\) factor for raw pairs, and the \(u^5\) loss in the modulus lower bound. For the second, raw four-leaf tuple counts are at most \(u^{40}2^{2\beta_j}\), and their exponent after filtering obeys \[ \begin{aligned} 2\beta_j-L_0-L_j &\le \frac n2+\left(-\frac52+3h_*\right)m+2\tau\\ &\le \frac n2. \end{aligned} \tag{36}\] The final inequality holds for large \(n\), since the excess is at most \(-.0658m+.0156n\), and \(m=.24n+O(1)\). For the third bound, the exponential part of the preceding universe count divided by the parent modulus is \[\frac r2+\overline H_0m+m-d_j-L_0 =\frac n2+(\overline H_0-1)m-d_j+f_0 \le\Lambda;\] the allocation’s logarithmic error and the modulus loss fit in the factor \(u^{10}\).

Let \(\mathcal E\) be the resource event \[ G\le u^{200}2^\Gamma,\qquad J_L+J_R\le u^{200}2^{n/2},\qquad U_L,U_R\le u^{200}2^\Lambda. \tag{37}\] The scales in (34) are fixed under the conditioning used in (35). Markov’s inequality and a union bound, followed by averaging over that conditioning, give \[ \Pr[\text{spread test passes and }\mathcal E^c] \le u^{-174}+u^{-149}+2u^{-190} <\frac1{10}u^{-100}. \tag{38}\] This is a joint failure estimate, not an estimate conditioned on the rare event in Lemma 12. Consequently that lemma’s surviving-representation event and \(\mathcal E\) hold together with probability at least \(.9u^{-100}\) in the low-mean YES case.

Three exponent relations control the subsequent costs: \[ \xi+\Gamma\le\frac n2,\qquad \Lambda+(1-h_*)m\le\frac n2,\qquad \xi-(\Lambda-.199n)\ge .0015n. \tag{39}\] The first relation pays for scanning the low-filtered children over roughly \(2^\xi\) tasks. The second pays for the repeated separator incidences of distinct records. The third makes the expected number of different-weight records in a solution bucket smaller than its capacity \(C\). These relations hold for large \(n\) on every passing setup. The first follows from \(.032-1.25+1.5h_*<0\), with cancellation of \(f_{\max}\). For the second, use \(\overline H_0\le h_*\) and \(f_0\le d_*\), since \(M_0\) has least deficiency. For the third, direct subtraction gives the lower bound \[-.051n+(1.032-h_*)m+d_*-f_0-f_{\max}.\] Here \(f_0\le d_*/2\), while the spread test implies \(f_{\max}\le d_*/2+.00025n\). Since \(1.032-h_*>.2206\) and \(m=.24n+O(1)\), this lower bound is at least \(.0015n\). The first two relations preserve the exact time exponent \(1/2\); no positive exponential slack is added there.

The extra prime and the solution bucket

Condition on a surviving representation and \(\mathcal E\), exposing all choices so far but still not \(q\). In its loop iteration, the expected number of entries in side \(j\)’s universe with weight different from \(x_j\) but congruent to it modulo \(P=p_0q\) is at most \[ U_j u^3 2^{-\xi} \le u^{203}2^{.199n-.0015n}. \tag{40}\] The nonzero difference must be divisible by the independent prime \(q\), so the prime collision bound applies. No coprimality of \(q\) and \(p_0\) is required. Since \(C\ge 2^{.199n-1}\), the right side of (40) divided by \(C/2\) is at most \[2^{(203/10^9-.0015)n+2}\] on the main branch. Markov’s inequality shows, with conditional probability at least \(.9\) for large \(n\), that both sides have at most \(C/2\) such different-weight entries.

Equal-weight entries need a separate argument. On L, at most \(\binom m{k_0}\le 2^{h_*m}\le 2^{.194736n}<C/2\) distinct entries can have weight \(x_L\), since the smaller top mask has size at most \(m/4\). Thus the entire solution L bucket fits. On R, follow the prefix of the solution top mask. At a full prefix there is at most one entry of weight \(x_R\), by deduplication. Together with the different-weight bound, this full-prefix bucket fits, so the solution’s prefix path terminates in a completed nonoverflow task. In every task compatible with the solution masks, its surviving leaf choices generate the corresponding parent entries. Hence the solution pair reaches a weighted disjointness check, unless an earlier YES or an operation or sampling abort has already occurred.

Applying the three prefix bounds

Consider the complete hypothetical parent schedule obtained by ignoring YES answers and the operation cap, while retaining the actual overflow rules. Its generation uses only the parent choices and \(q\). Thus it can be fixed without examining any separating family. The three bounds in Lemma 9 now have their required numerical inputs; we apply each to the quantity it controls.

First, the number of parent-generation tasks is at most \[ T\le 2q+2(m+1)U_R/C\le u^{203}2^\xi. \tag{41}\] Indeed, \(q\le2^\xi\), \(C\ge2^{.199n-1}\), and the last inequality in (39) gives \(U_R/C\le2u^{200}2^{\xi-.0015n}\) on \(\mathcal E\). The main-branch guard absorbs the remaining polynomial factor.

Second, the concrete stopped-stream implementation supplies \[ H=u^8(2^{.2n}+G),\qquad K=u^8 \tag{42}\] in the task-cost formula of Lemma 9. The term \(H\) pays for regenerating the leaves, prefix tests before streaming, sorting, stream initialization and traversal, the bounded tie buffer, and dictionary initialization. The term \(K\) pays for each potential matching tuple, including replay, invalid local overlaps and repeated entries. Consequently the full parent-generation work is at most \[\begin{aligned} H T+K\bigl(J_L+(m+1)J_R\bigr) &\le u^{211}2^\xi(2^{.2n}+u^{200}2^\Gamma) +u^8\bigl(J_L+(m+1)J_R\bigr)\\ &\le u^{420}2^{n/2} \end{aligned}\] for sufficiently large main-branch inputs. Here \(\xi+.2n<n/2\) follows from \(\xi\le.25768n\), whereas \(\xi+\Gamma\le n/2\) is the first exact relation in (39). The raw-match term is charged by prefix depth; it is never multiplied by \(T\).

Third, write \(N_{\mathrm{check}}\) for the total array length supplied to all final checks, counting every reuse of a left array. The final bound of Lemma 9 gives \[ N_{\mathrm{check}}\le U_L+(2m+3)U_R. \tag{43}\] Completed right chunks pay for their own entries, and overflow entries pay for repeated left arrays. This is why the final checks use the distinct-entry counts \(U_j\), even though generation required the raw counts \(J_j\).

Independent families and bounded-trial success

Fix all choices through \(q\), on the joint survival, resource and bucket events. Choose deterministically the check on the completed solution-prefix path and the solution pair in it. The complete hypothetical check list, its layout parameters, this designated check and its pair are all functions of those nonfamily choices. Conditional on the layout, the program sampled the four indexed families from the product law specified in Section 5, independently of every parent and filter choice. Therefore that same product law holds after conditioning jointly on this entire list, its parameters, and the designated pair. This fact, rather than delayed exposure by itself, verifies the hypothesis of Corollary 11.

On \(\mathcal E\), (43) and that corollary give conditional expected total check work at most \[N_{\mathrm{check}}u^{22}2^{(1-h_*)m} \le u^{230}2^{\Lambda+(1-h_*)m} \le u^{230}2^{n/2}.\] The second exact relation in (39) is used here. Markov’s inequality bounds the chance of exceeding \(u^{240}2^{n/2}\) operations by \(u^{-10}\). The designated pair has coverage probability at least \(1-4e^{-10}\). A union bound gives both coverage and this work bound with conditional probability at least \(1-4e^{-10}-u^{-10}\); these events need not be independent. The hypothetical list is an analysis device and is never stored.

Bounded sampling and its exact law

An ideal draw is uniform on its specified finite set, using fresh randomness conditional on the preceding choices. The implementation uses a fixed attempt limit. We couple it to the ideal experiment, rather than condition the whole experiment on every sampler succeeding: that latter conditioning could bias earlier adaptive choices.

On the main branch, \(\log u\le n/10^9\), so the coupling loss is smaller than any fixed multiple of \(u^{-110}\) for large \(n\). A watchdog interruption does not create an additional probabilistic assumption. On successful coupling, all sampled choices agree with the ideal choices, while the cost estimates already allow the worst permitted number of attempts. The favorable work events therefore complete before the watchdog; other executions may simply abort.

Exact word operations

The program scans the input and counts magnitude bits by shifts to obtain \(b\). Actual signed weights, the transformed target and all relevant differences have magnitude less than \[2^{b+\lceil\log(n+2)\rceil+4}.\] Even an invalid parent tuple uses an input index at most twice, so the same bound covers the quantities considered before disjointness is checked. Store a sign and a magnitude, with canonical zero. Signed addition, comparison and normalized remainders are implemented on these fields. When combining an actual weight with a residue, reduce the weight first. A fixed-width signed weight followed by the relevant mask bits supplies the trie key.

Every mask has at most \(n\) bits, and every stored item has a constant number of word fields. Binomial coefficients on at most \(n\) elements can be computed multiplicatively; immediately before division the intermediate integer is at most \(n2^n\). Floor logarithms are bit lengths. Hence the background allocations, modulus parameters and rational floors are exact integer computations. The separator quantity \(3^m\) fits in a word as well. Feasibility tests precede unsigned subtractions, or those quantities are represented with a sign. No entropy or real-arithmetic oracle is used by the program.

The largest product modulus satisfies \(P\le2^{s+.258n}\). Residue arithmetic therefore fits in a word, and trial division compares the candidate divisor with the corresponding integer quotient instead of forming a potentially unnecessary square. Masks for range sampling use fewer than \(w\) bits. The main-branch guard also gives \[\log\bigl(u^{500}2^{\lceil n/2\rceil}\bigr) \le (1/2+500/10^9)n+1<w,\] for large \(n\). Thus fuel, the \(u^{120}\) round count, intermediate powers, timestamps and counters have bounded word width. The compact memory addresses fit by the space calculation below. All arithmetic invoked as a unit-cost operation stays within the stated word model.

Permutations, sign masks, moduli, residues, family masks and replay state remain in the counted workspace whenever reused. Once a random value is discarded, the program never reads it again.

Space on every random outcome

We specify the simultaneous storage terms, rather than infer space from the favorable resource event. Let \(L_{\max}=2^{.185n}\), an upper bound on every raw representation leaf list on the main branch. There are only eight such lists; an item, heap cell or stream-row state occupies constantly many words. Linear auxiliary arrays suffice for sorting. Hence the stored leaves, heaps, row states and a constant number of replay snapshots occupy \(O(L_{\max})\) words. The tie buffer uses \(O(B)\) words. Initial compressed-block lists and mixer-counting half lists have sizes \(2^s\le2^{.12n}\); the compressed trial’s stored sublists have size at most \(2^{.14n}\). These fit the same bound, and the two trials run sequentially.

A dictionary keeps at most \(C\) distinct records and stops when a \((C+1)\)st key is encountered. Its fixed-width keys have \(O(u)\) bits, so the binary trie, including transient nodes for that rejected key, has \(O(u(C+1))\) nodes. Each node has constantly many word fields. At most a constant number of dictionaries and retained parent arrays coexist. In the right prefix search, an overflowing task’s workspace is discarded before its children are processed. An \(O(n)\)-depth stack stores prefixes and return information, not all previous task dictionaries. The completed left array is retained while the current right task or final check runs.

For the final check, the four family-index trees have total active depth \(O(n)\); every depth keeps constantly many arrays of length at most \(C\). These are actual \(O(nC)\) retained record buffers, including linear sorting workspace, as in (26). Caller-retained parent arrays contribute another \(O(C)\), already covered by this bound. The incidence tables have eight lists per block mask across the four blocks, each of length at most \(10\cdot2^g+1\). Their total capacity is at most \[8\,2^g(10\cdot2^g+1)=O(2^{2g}).\] Each stored index uses at most \(g+4\) bits, and each family mask uses \(g\) bits, so both fit in one word. Directories and sampled families add only \(O(2^g)\) words. The incidence contribution has the smaller exponential factor \(2^{2g}\le2^{.12n}\).

Combination generation, permutations, sampler state, integer parameters, prefix and interval control, counters, and a conservative binomial workspace use \(O(u^2)\) further words. In particular, none retains the hypothetical check list. Combining all terms, some absolute implementation constant \(K\) bounds simultaneous storage by \[K\bigl[u(C+1)+(n+1)C+L_{\max}+B+2^{2g}+u^2\bigr].\] Now \(C\le2^{.199n}\), \(L_{\max}\le2^{.199n}\), \(B\le2^{.199n}\), \(2^{2g}\le2^{.199n}\), and \(n\le u\). Term by term this proves the required conservative bound \[ O\bigl(u^{15}2^{.199n}\bigr) \tag{44}\] on every random outcome, including an overflowing or aborted trial. No assumption about average bucket size or \(\mathcal E\) was used. Its address bit length is at most \(.199n+15\log u+O(1)<w\) on the main branch. Allocation and stack pointers are reset between tasks and trials; entries are initialized when reused. Even clearing the allocated storage linearly is below the trial time budget, so aborts accumulate neither stored data nor uncharged cleanup work.

A finite program, amplification and the theorem

There are finitely many sufficiently-large conditions in the argument, with absolute constants and fixed polynomial degrees. The main-branch guard makes each fixed exponential margin dominate the required polynomial factors uniformly in that branch. Choose one absolute integer \(n_0\) meeting all these conditions and fix it in the program, independently of \(c\).

Small-word inputs need not hold \(n_0\) as a word. Place an exact subset-enumeration routine near the beginning of the finite program. Unroll the binary digits of \(n_0\), from least to most significant, using only literals zero and one. Maintain a shifted copy of \(n\) and a three-valued comparison state. At each digit, compare its low bit with the fixed threshold digit, replace the comparison state when they differ, and shift the copy right. A newly seen difference has higher significance. If the copy becomes zero before the threshold’s leading digit has been processed, branch to the nearby exhaustive routine. After that leading digit, a nonzero remaining copy means \(n>n_0\); otherwise the comparison state decides.

A short input executes only \(O(1+\log n)\) adjacent digit stages before exiting. Its instruction addresses and state therefore remain small; it never loads the full threshold or a distant main-program address. Once \(n\ge n_0\), enlarge this fixed threshold if necessary so that all other fixed literals and main-program addresses fit. The second guard, (2), is then an integer comparison. Both exceptional cases use exact enumeration with an \(n\)-bit subset counter and \(O(n)\) words. This is one finite program with no advice and no input for the exponent \(c\).

On a main-branch YES input, Lemma 7 gives constant success probability when \(\mu\ge.00765n\), and Lemma 13 gives probability at least \(u^{-110}\) when \(\mu<.00765n\). Both trials run in each round with fresh words and reset state. Thus each round succeeds with probability at least \(u^{-110}\), also conditional on every previous round failing. After \(u^{120}\) rounds the probability of missing a solution is at most \[(1-u^{-110})^{u^{120}}\le e^{-u^{10}}<1/3.\] Every YES is an exact valid match by Lemma 8; the sign-toggle identity certifies an original solution. The exceptional branch is exact, so correctness holds on every individual input.

Instrument each trial with a counter for underlying word operations. Its constant overhead, stopping and reset give per-trial time \(O(u^{500}2^{\lceil n/2\rceil})\) on every outcome. Input scanning and the initial guards take polynomial time in \(u\). All trial preprocessing, sorting, table construction and sampling are charged. The total main-branch time is consequently \[O\bigl(u^{620}2^{\lceil n/2\rceil}+\operatorname{poly}(u)\bigr).\] For every fixed positive integer \(c\), all sufficiently large inputs with \(b\le n^c\) avoid the exceptional branch and have \(u=\operatorname{poly}_c(n)\). This time bound and (44) hold simultaneously for every random outcome. Together with the correctness argument they prove Theorem 1. Finally, for each fixed \(\rho>.199\), the factor \(u^{15}=\operatorname{poly}_c(n)\) is absorbed by \(2^{(\rho-.199)n}\), proving Corollary 2; the polynomial factor remains at the endpoint \(.199\).