PaperlayerView exact revision on arXiv

Source-linked AI summary

Subset Sum and Integer Programming Feasibility Test in Near-Optimal Time

Lin Chen, Yuchen Mao, Guochuan Zhang

arXiv:2610.12953v1cs.DS

TL;DR

Subset Sum has long posed the question of whether it can be solved in linear time. This paper uses higher-dimensional structure and recursive boundary processing, and gives a randomized algorithm for the one-dimensional set case running in Oε,c(N^(1+ε)) time with error probability at most N^-c.

  • Problem

    The paper addresses the search for pseudopolynomial algorithms with a small exponent of N.

    Source: §1 · p. 3

  • Method

    The approach uses additive structure in higher-dimensional coordinates and recursively processes zonotope-boundary subproblems.

    Source: §1.4 · p. 9, §1.5 · pp. 13–14

  • Results

    Oε,c(N^(1+ε)) time, with error probability at most N^-c, for randomized set Subset Sum.

    Source: §1.5 · p. 11

  • Takeaways & Limitations

    Proximity can cap multiplicities before expansion, yielding a feasibility algorithm for integer programs with finite lower and upper bounds.

    Source: §1 · p. 3

    The dependence hidden in Od,ε is not estimated; the conclusion concerns the exponent of N.

    Source: §11 · p. 94

Abstract

from arXiv · show

Given an integer $t$ and a set of integers in $[N]$, Subset Sum asks whether there exists a subset that sums to $t$. A long open problem is whether Subset Sum can be solved in $O(N)$ time. We show that Subset Sum can be solved in $O(N^{1 + \varepsilon})$ time where $\varepsilon > 0$ is an arbitrarily small constant. Our result also generalizes to multi-sets in multi-dimension. That is, for any fixed $d$ and $\varepsilon >0$, the $d$-dimensional subset sum can be solved in $O(n + N^{d + \varepsilon})$ time. As an application, for any fixed $d$ and $\varepsilon$, feasibility test of integer programming with $d$ constraints can be done in $O(N^{d+\varepsilon} \mathrm{poly}(\ell_{\mathrm{in}}))$ time, where $N$ is the maximum absolute value in the constraint matrix and $\ell_{\mathrm{in}}$ is the input size. Although the algorithm is quite involved, its high-level idea is clear. It is already known that when the input set is dense and $t$ lies in the interior of the zonotope, then Subset Sum is easy to solve [Galil-Margalit '91, Bringmann-Wellnitz '21, Chen-Hu-Mao-Zhang '26]. Our key observation is that a sparse input can exhibit a dense structure when lifted to higher dimension. We show that such a lifting can be done efficiently. After lifting, the interior of the zonotope is easy to tackle, and one only needs to deal with the thin area near the boundary of the zonotope. Then we show that the boundary area can be decomposed into subproblems and solved recursively, and that there cannot be too many recursion levels since each level of recursive reduces the volume of the area significantly.

AI disclaimer

The authors designed the main proof route for one-dimensional Subset Sum, while GPT Astra Ultra helped turn their insights into complete proofs. GPT also contributed to generalization, drafting, and verification, with the authors retaining responsibility for the paper.

AI disclaimer

  • The authors designed the proof route: extracting additive structure, lifting to constant dimension, and splitting the search between a zonotope’s interior and boundary.The framework builds on a recent dense-regime multidimensional subset-sum paper coauthored by the authors.Source: AI disclaimer · p. 1
  • GPT Astra Ultra helped complete the mathematical proofs; when it struggled with several lemmas, the authors resolved the difficulties by contributing ideas.A research note documents conversations between GPT and the first author.Source: AI disclaimer · p. 1
  • GPT generalized the randomized one-dimensional algorithm to deterministic multidimensional multiset algorithms without author guidance, drafted the paper, and verified the main results using Lean 4.The authors take full responsibility for the paper’s content, technical claims, and integrity.Source: AI disclaimer · p. 1

1 Introduction

The introduction outlines algorithms for subset sum and bounded integer-programming feasibility, using higher-dimensional lifts to exploit additive structure and recursively handle boundary regions. It also describes ways to control dimension growth and recursive work.

1 Introduction

  • The bounded integer-programming problem generalizes multidimensional subset sum: its binary-variable form asks whether the columns of A can be selected to sum to the target.For finite variable bounds and binary-encoded multiplicities, the paper obtains feasibility by reducing relevant ranges before expanding copies.Source: §1 · p. 3

1.1 Subset sum

  • Deterministic one-dimensional subset sum takes O_ε(n + N^(1+ε)) time for explicitly listed signed integers with unrestricted multiplicities.This gives near-linear dependence on n and an arbitrarily small fixed polynomial overhead in the maximum absolute input value N.Source: §1.1 · p. 4, §1.3 · p. 6

1.2 Multidimensional subset sum and integer programming

  • For fixed d and ε > 0, bounded integer-programming feasibility takes O_d,ε(N^(d+ε) poly(ℓin)) time and returns a feasible vector when one exists.The polynomial degree in the input length is absolute, and the result covers binary-encoded finite variable bounds.Source: §1.2 · p. 5, §1.3 · p. 6

1.3 Our contribution

  • For fixed d and ε > 0, arbitrary vector multisets with coordinates bounded by N admit deterministic subset-sum algorithms in O_d,ε(n + N^(d+ε)) time.The theorem allows unequal coordinate bounds, unrestricted multiplicities, and requires the same selection of items to satisfy every coordinate.Source: §1.3 · pp. 5–6
  • A constructive structural theorem partitions signed multisets into exceptional items and a lifted multiset whose attainable sums contain a filled inner region within a controlled zonotope enlargement.The exceptional subset sums combine exactly with the lifted sums to recover the original subset sums.Source: §1.3 · p. 7
  • The scalar algorithm also yields deterministic bounds for equal-sum Partition and optimal two-machine makespan, in time near-linear in n plus N^(1+ε).For scheduling, feasibility of a makespan bound is reduced to a subset-sum query, with binary search used for optimization.Source: §1.3 · p. 8

1.4 Additive structure and the algorithm

  • The algorithm exploits the fact that sparse subset sums may have generalized arithmetic-progression structure that becomes geometric after lifting to higher-dimensional coordinates.It combines filled lattice regions inside zonotopes with recursive boundary reductions, without requiring the original scalar input to be dense.Source: §1.4 · p. 9
  • A structural step represents most items in a constant-dimensional progression and uses a reserved subset to certify a filled lattice core, while retaining an uncertified boundary for further computation.Exceptional-item contributions are computed exactly; the method does not require the entire zonotope to be filled.Source: §1.4 · pp. 9–10
  • When projection-created holes persist, the algorithm adds a coordinate recording a thin direction; constantly many such introductions and shrinking boundary regions keep the computation within N^(1+ε) time.For multisets, a preliminary proximity reduction bounds relevant residual multiplicities without expanding large multiplicities during geometric recursion.Source: §1.4 · p. 11

1.5 Overview of the set algorithm

  • For every fixed ε, c > 0, a randomized algorithm decides set Subset Sum on A ⊆ [−N, N] ∩ Z in Oε,c(N^(1+ε)) time with error probability at most N^(−c).Source: §1.5 · p. 11
  • Boundary reductions use reference selections and signed color coding to handle heavy-item changes while preserving feasible targets, producing children whose total enclosing-array size is at most w/2.Source: §1.5 · p. 13
  • For buffered interior targets, a lattice point in a filled core certifies attainability; otherwise, filtering rules out targets or exposes a thin direction and produces an instance of dimension d + 1.The filled-core correction uses the reserved items together with rounded unreserved selections.Source: §1.5 · pp. 14–15
  • An unresolved boundary patch is encoded by appending an independent coordinate and retaining a constant-width band, yielding a child instance of rank d + 1.The added coordinate records the previously hidden direction; the band keeps only O_r(1) values per old target.Source: §1.5 · p. 16, Figure 4 · p. 17
  • The short-relation invariant bounds both current dimension and total dimension lost under deletions by Oδ(1), so only Oδ(1) independent coordinates are added per branch.The invariant preserves signed k-sum equalities in both directions across representations.Source: §1.5 · pp. 17–18
  • The current dimension is constant because independent vectors generate distinct short nonnegative combinations, while their scalar sums remain in the fixed range [−N, N].The comparison uses k as a fixed positive power of N.Source: §1.5 · p. 17
  • Boundary children have total size at most w/2, while other transitions increase summed size by at most a polylogarithmic factor and occur only constantly many times per branch.The progression construction costs eOδ(hw) when h ≤ τ0.Source: §1.5 · p. 18

2 Preliminaries

The preliminaries establish notation, additive-combinatorial and geometric tools, and the recursive vector-item subset-sum framework. They also give exact subset-sum procedures for the recursion, including randomized signed-budget computation, item transfer, and a stopping rule for small residual instances.

2.1 Preliminaries and notations

  • The notation distinguishes repeated addition kX from geometric dilation k·X and counts each input occurrence as a separate item, including repeated values.For example, 2{0, 1} = {0, 1, 2}, whereas 2·{0, 1} = {0, 2}.Source: §2.1 · p. 19
  • The GAP toolkit combines long-sumset structure without density assumptions [1], constructive bounded-rank progressions for small-doubling sets [2], and properization [3].Properization ensures unique coefficient representations throughout the required dilation, with only a constant-factor increase in coefficient volume for fixed rank and dilation.Source: §2.1 · pp. 20–21
  • For dense sets Ai with |Ai| ≥ c|B ∩ Zr|, 0 ∈ Ai, and spanZ Ai = Zr, the filling result covers every lattice point of a large translated box [1].When |kU| ≥ 2|S|, some u ∈ U contributes many new sums as an optional additional item.Source: §2.1 · p. 21
  • Fixed-dimensional convex optimization can return either a lattice point or a bounded-width integer direction, which respectively certifies a solution or supplies a new coordinate.The lattice basis reduction and Macbeath-overlap tools support geometric boxing and boundary-cover arguments.Source: §2.1 · p. 22

2.2 Representation of recursive instances

  • Each recursive call asks whether current vector items contain a subset summing to an exact retained target; changing the reference subset signs items and translates the target set.A flip adds an item when its reference bit is 0 and removes it when that bit is 1.Source: §2.2 · p. 23
  • A linear map recovers changes in original scalar sums from current vector sums, but because it may be noninjective, the recursion tests exact vector targets.With distinct original integers, a current vector has multiplicity at most two.Source: §2.2 · pp. 23–24

2.3 Exact Boolean operations and signed color coding

  • With probability at least 1−ξ, the randomized signed-budget algorithm retains every absolute-bounded sum while reporting only actual subset sums inside the budget box.Absolute budgets keep every subset sum of a qualifying selection inside that box, including intermediate sums for signed item coordinates.Source: §2.3 · p. 25
  • Removing a subset of items preserves the answer exactly when its subset-sum shifts are transferred to the target set.For e=O(τ), the transfer takes eO_d(e+w) time, allowing a constant enlargement of the allocated box.Source: §2.3 · p. 25
  • When at most τ items remain, an exact Boolean product computes their full subset-sum support and tests whether it intersects the target set.The resulting computation fits the stated eO_d(n+w) bound for the enclosing array size.Source: §2.3 · p. 26

3 Preprocess Input

Preprocessing places retained inputs in common bounded-rank GAP coordinates, separates outliers and a reserve, and constructs a filled box with a linear map back to the current vectors. The reserve corrects rounding so lattice points in an inner zonotope become actual subset sums, while vector inputs are encoded as positive scalar items by an exact change of variables.

3 Preprocess Input

  • For vector inputs, an injective mixed-radix encoding on an enlarged symmetric box maps items to scalars, and sign flips with target translation preserve the subset-sum instance exactly.The encoding is applied before GAP calls; complemented labels and multiplicities are tracked so recovered selections respect the original copies.Source: §3 · p. 27
  • For fixed η,d0>0 and integer h≥hη, a randomized algorithm returns with high probability a partition A=E⊎R⊎B (or E=A,R=B=∅), with |E|=Oη,d0(h log²(h_amb+2)) and |R|=Oη(h).When constructed, R∪B has coefficient vectors in a rank-Oη(1) GAP; reserve subset sums contain a translated lattice box on which ρ is injective.Source: §3 · p. 27
  • The reserve corrects rounding of at most r fractional GAP coefficients, turning lattice points in a shifted inner zonotope into actual subset sums using disjoint input copies.The reserve supplies the offset plus the rounding error after the fractional coefficients are rounded to zero or one.Source: §3 · p. 28
  • Fixed-rank properization constructs a symmetric t-proper GAP containing the input GAP with coefficient-box cardinality O_r,t(vbox), in time polynomial in the description bit length.The common-lattice boxing lemma supplies an entire-lattice basis and a containing box whose dilated lattice-point counts grow by only a rank-dependent constant factor.Source: §3 · p. 29
  • The construction builds a common proper GAP, protects real rank against deletions, and forms dense greedy blocks; restarts reduce the repeated-sumset size, while consecutive blocks with a common lattice form the reserve.Each block uses O_eta(h) items and has at least mph/4 subset sums; the phase construction bounds the outliers across restarts by O_eta,d0(h log^2(hamb + 2)).Source: §3 · pp. 30–31
  • The preprocessing produces a reserve whose subset sums fill a translated box in GAP coordinates, where the encoding is injective.Predecessor witnesses make the translate constructive; only the constructive Freiman calls need randomization.Source: §3 · p. 32
  • An explicitly computable integer matrix F recovers every retained vector from its GAP coordinates and satisfies λF = ρ.Filled-box witnesses and injectivity on sums of O(h) old items imply that the recovery map is affine on the box.Source: §3 · pp. 32–33
  • The filled box is essential to the recovery argument; a scalar progression in projected reserve support or bounded-order properness alone does not justify F.Source: §3 · p. 33

3.1 From a filled box to a filled zonotope

  • With a reserve R of q items, every lattice point z satisfying z + q · C ⊆ Z(U) is a subset sum of U.Rounding at most r fractional coefficients leaves an error in r · C ∩ Λ, which reserved items correct; for multiplicities stored as counts, the argument needs no expansion into copies.Source: §3.1 · pp. 33–34

4 The normal boundary reduction

The normal boundary reduction organizes boundary targets into buffered interior, infeasible, and normal patches, then transfers bounded heavy-item choices into filtered residual problems on light items. Rank restriction and rounding preserve scale as these children are verified in both directions, with the reduction bounding their size and scan costs while retaining assigned parent solutions with probability at least 1 − ζ.

Why the instance has a set of targets

  • Removing items creates an exact set of residual targets, one for each subset choice of the removed items; later lifts preserve the permitted vector targets and coordinate conditions.The recursive question is whether surviving items sum to any point in that target set.Source: §4 · p. 37

Input assumptions

  • Target arrays store the exact permitted targets in a full enclosing coordinate box, counting zero entries as well as allowed targets.Residual targets outside the real span of surviving items can be discarded because those items cannot sum to them.Source: §4 · pp. 37, 41

Normal boundary patches

  • Cells failing the buffered-interior test are covered by normal boundary patches whose regions adapt to the nearby zonotope boundary.Small regions are packed disjointly inside a thin boundary shell to bound their total volume; enlarged covering regions may overlap.Source: §4 · pp. 39–40

Reference selection and changes of sign

  • For each patch, supporting-normal deficits bound the total contribution of selection flips, so a feasible selection can flip only O_d(τ) heavy copies.The heavy-item support computation retains all heavy-flip sums needed by feasible selections with high probability.Source: §4 · p. 39

Transferring the heavy choices

  • The child target set is U_x = (T_x − b) − S_x, combining each assigned parent target with retained heavy-flip sums before removing the heavy items.This transfer is sound because heavy witnesses and child solutions use disjoint items, and complete with high probability when the support retains a parent solution’s heavy-flip sum.Source: §4 · p. 41

Lemma 4.1 (Normal boundary reduction)

  • The reduction partitions targets into buffered interior patches, infeasible cells, and normal boundary patches; normal patches yield sound children whose total array size is at most w/2.Every parent solution assigned to a normal patch survives in some child with probability at least 1 − ζ; children use subsets of the original items, with signs possibly changed, and retain scale τ.Source: §4 · p. 43

Lemma 4.2 (Local lattice boxing)

  • Local lattice boxing encloses a convex body in a coordinate box whose lattice entries are controlled by its volume in lattice units.The enclosing box uses a basis of the entire lattice, and outward integer rounding costs only a dimension-dependent factor.Source: §4 · pp. 43–44

Packing the normal boundary patches

  • Disjoint small regions in a thin boundary shell are enlarged to cover boundary candidates, bounding total child-array space by the shell’s volume.Macbeath overlap and engulfing properties provide the cover, while lattice boxing converts the packed-volume bound into an array bound.Source: §4 · pp. 45–46

Rank restriction and integer rounding

  • After heavy-item choices are transferred to shifted targets, residual targets are restricted to the surviving items’ span before projection, preserving the exact decision problem.Projection retains the exact residual target set; filtering off-span targets first prevents projection from introducing false attainable targets.Source: §4 · pp. 41, 42, 45

Choosing support directions for each local box

  • Zonotope rows encode nonnegative selection deficits, while artificial box rows bound changes in other directions and keep them within the target window.These permissible support directions connect the local parallelepiped to subset sums, enabling bounds on heavy-item changes.Source: §4 · pp. 45, 47

The normal boundary reduction

  • The heavy-item support computation retains required bounded flip sums with high probability; filtering preserves required sums and removes entries exceeding final row bounds.The filtered support is subtracted from the shifted local target set, transferring heavy choices into residual targets while all heavy items are removed.Source: §4 · pp. 49–50
  • The light-item deficit test is necessary for residual solutions, and the residual targets and scaled surviving items fit one common local box centered at r0.The box enlargement constants depend only on d and abuf, not on ϑ or η.Source: §4 · p. 51
  • Restricting to the survivors’ span before integer rounding preserves τ and bounds the child array size by a dimension-dependent multiple of the local patch size.The order avoids widths below one before projection, which otherwise could introduce a factor depending on 1/η.Source: §4 · p. 51
  • A child solution yields a valid parent solution, and every parent solution survives in the child with the stated high probability, subject to a union bound over patches.The summed child-array costs are paid for by the packed-volume estimate.Source: §4 · pp. 51–52
  • For fixed d, constant candidate, patch, and geometry-query counts make input scans cost eO(n) and the global target scan cost eO(w).The passage also states that local Boolean computations cost eO, but the bound is truncated in the supplied text.Source: §4 · p. 52

5 The interior reduction

For targets well inside the zonotope, the interior reduction either resolves the instance or creates an equivalent instance with one additional coordinate. It retains an exact target set in a child array of O(w) entries and takes eO(n + w) time, excluding common GAP construction.

5 The interior reduction

  • A common GAP supports searching for an integer point mapping to a target; if that search fails, a bounded-width direction supplies one additional coordinate.The target region has a substantial buffer inside the zonotope, and the child array remains comparable in size.Source: §5 · pp. 52–53
  • Under the stated hypotheses, the interior reduction either resolves the instance or produces one equivalent instance of actual vector rank d + 1, with an exact target set in an O(w)-entry lattice box.Excluding the common GAP construction, the reduction takes eO(n + w) time.Source: §5 · p. 53
  • The reduction applies a point-or-thin-direction test to a fiber: a lattice point yields a subset sum, while a thin direction supplies a functional for the lift.The fiber is formed from the GAP-coordinate zonotope above an actual target; an integer point in it gives a solution.Source: §5 · pp. 53–54
  • The lift transfers the reserve and high-price items to the exact target set, then encodes surviving-item endpoint deficits in a new coordinate restricted to a band of width 2κ.The child target set retains the old target coordinates and keeps precisely the new-coordinate values specified by the proved band.Source: §5 · pp. 55–56
  • The reduction is sound and complete: child solutions reconstruct parent subsets, and every parent witness yields a child target retained by the lift.The new coordinate is independent of the old ones, so the map has rank d + 1.Source: §5 · p. 56

6 Bounding dimension changes

The section bounds dimension changes using an invariant that preserves short signed sums throughout the algorithm. It shows that both current rank and rank loss along a path are bounded by constants depending on δ, limiting exceptional transitions.

6 Bounding dimension changes

  • The short-relation invariant preserves signed k-sums across lifts, deletions, sign changes, and injective coordinate changes.It permits progress to be measured using the original integers even as the working dimension changes.Source: §6 · pp. 57–58
  • Under this invariant, current rank is at most d*, and the sum of rank losses from item deletion along any path is at most q*.The rank bound follows from the count of distinct nonnegative combinations of independent item vectors.Source: §6 · pp. 58–59
  • There are at most r* exceptional transitions along a path, including coordinate introductions and separate rank-loss transitions.The bound is Oδ(1), while normal boundary reductions may still occur many times.Source: §6 · pp. 58–59

7 The recursive algorithm

The recursive algorithm classifies targets into normal boundary patches and buffered interior patches, then applies the corresponding reductions while retaining exact target sets. Conditional on complete color-coding calls and successful verified GAP constructions, it answers correctly; unconditionally, it has no false positives.

7 The recursive algorithm

  • The recursion is correct conditional on complete color-coding calls and successful verified GAP constructions, and it has no false positives unconditionally.Accepting branches use actual input copies, while the stated completeness events ensure feasible targets are retained.Source: §7 · pp. 59–60
  • At each node, targets are classified into normal or buffered interior patches; normal patches use heavy-item reductions, while interior patches use preprocessing, a common GAP, and the interior reduction.The algorithm retains exact shifted-and-filtered target sets, and normal child array sizes sum to at most half the parent size.Source: §7 · p. 60
  • The buffered interior step applies when the target window retains a substantial buffer inside the surviving zonotope after excluded items are transferred.The exclusion count is e = O(h log^2 N) = o(τ), so the stated buffer hypotheses hold for sufficiently large N.Source: §7 · p. 60
  • Fresh randomness and summable conditional error allowances bound the probability of missing any required absolute-bounded sum during recursion by ξ.Stored product-tree supports allow recovery of a selected subset for a retained sum without requiring witnesses for every sum.Source: §7 · p. 60

8 Bit complexity, termination, and running time

The analysis bounds stored coordinates and lattice data at each fixed-dimensional recursive node, establishes scale and transition bounds, and uses array-size reductions to control recursion. With summable failure probabilities, the algorithm has error at most N^-c and no false positives.

8 Bit complexity, termination, and running time

  • At a fixed-dimensional node with item coordinates and w bounded by N^Oδ(1), stored coordinates and lattice data use Oδ(log N) bits per entry.Geometric and lattice operations take n polylog N bit time, excluding Boolean-array operations.Source: §8 · p. 61
  • All calls meet the polynomial-scale hypothesis, properness scales exceed 2k, and each path has at most r* = Oδ(1) exceptional transitions.The argument verifies a finite prefix before applying the rank bound, rather than presuming the dimension bound.Source: §8 · pp. 61–62
  • Normal steps reduce total child array size to at most half the parent size, while the number of recursion nodes is polynomial and normal-only paths terminate.The normal forest has geometrically bounded total array size; exceptional levels increase that bound by at most a polylogarithmic factor per level.Source: §8 · p. 62
  • Assigning summable conditional failure probabilities gives error at most N^-c without false positives, while bounded repetition or prescribed timeouts preserve the running-time bound.The correctness guarantee follows from the recursion lemma and a union bound.Source: §8 · p. 63

9 Extension to multisets

This section extends the subset-sum reductions and algorithm to multisets, accounting for multiplicities while controlling boundary work, dimension changes, and recursive instances. It establishes correctness and running-time guarantees, including for binary-encoded multiplicities.

9.1 Multiplicities and the preliminary reduction

  • Counts represent repeated types, and copies are explicitly listed only when a preceding bound limits their number, so recursive work can depend on distinct values.The algorithm selects no more copies of a type than the input contains.Source: §9 · p. 63, §9.1 · p. 63

9 Extension to multisets

  • For fixed ε, c > 0, the randomized multiset algorithm decides subset sum in Oε,c(n + N^(1+ε)) time, with failure probability at most N^-c and no false positives.It applies to explicitly listed multisets in [−N, N] without restrictions on distinct-value count or multiplicities.Source: §9 · p. 63

9.1 Multiplicities and the preliminary reduction

  • In O(n + N) word operations, normalization yields an equivalent instance with target in [0, N − 1], at most 2N nonzero signed types, multiplicity at most 2N per type, and at most 4N² total copies.The reduction records how to reconstruct original feasible counts.Source: §9.1 · p. 64

9.2 The boundary reduction for multisets

  • The multiset boundary reduction runs in eO(m + w) time; every child solution yields a parent solution, and each feasible target assigned to a normal patch remains feasible in a child with probability at least 1−ζ.Each child retains whole surviving types with their multiplicities, possibly with changed signs; working with counts preserves the contraction in total target-array size without scanning every copy.Source: §9.2 · p. 66
  • The multiset boundary reduction uses constantly many patches, with total expanded-input and local-array costs O_d(w), and establishes the claimed running time and completeness probability of at least 1−ζ.Source: §9.2 · p. 69

9.3 A GAP construction for arbitrary multiplicities

  • The construction scans distinct values and records selections by decreasing counts, so its running-time dependence is on the number of distinct values rather than expanded multiplicities.Source: §9.3 · pp. 70–71
  • For arbitrary multiplicities, the randomized construction outputs a bounded-rank common GAP, an Oη(h)-copy reserve filling a γh-scaled box, witnesses, and rank robustness to d0h further deletions.Its structural output is correct with probability at least 1−(hhamb + 2)−b for any prescribed constant b > 0.Source: §9.3 · p. 70
  • The filling is verified using actual GAP-coordinate sums: Boolean correlation finds a translation, and predecessor data reconstructs reserve-copy witnesses for every point.Each selected block has support of size at least mph/4 and consists of sums using distinct selected copies, including when copies share a type.Source: §9.3 · pp. 73–74
  • The filled GAP translate yields distinct scalar subset sums from q = Oη(h) reserved items, all within an interval of length at most qN.Source: §9.3 · p. 75
  • An explicitly computable integer matrix recovers each retained type’s old vector from its GAP coordinates, enabling coordinate changes without separate work for repeated copies.For every retained live type, F u_i = v_i, and the map’s construction fits the stated bound.Source: §9.3 · p. 76

9.4 The interior reduction for multisets

  • Under its buffered hypotheses, the multiset interior reduction either resolves feasibility or gives one equivalent instance of actual vector rank d + 1 with an O(w)-entry lattice box.The child uses surviving original copies, possibly reoriented, and an exact target set.Source: §9.4 · p. 77
  • The reduction respects each type’s multiplicity by rounding within its available counts and correcting with reserved copies, without expanding repeated items.Apart from the common GAP construction, it costs eO(m + w) operations under the stated polynomial-boundedness conditions.Source: §9.4 · pp. 77–78
  • The interior multiset reduction allocates an O(w)-size array while materializing only O(h) removed copies.The lifted basis-coordinate box and rounding preserve the array-size bound; weighted support-oracle evaluations cost O(m), and the stated bit and time bounds follow when total multiplicity is polynomial in N.Source: §9.4 · p. 81

9.5 Bounding dimension changes for multisets

  • For fixed δ, the multiset recursion has Oδ(1) genuine coordinate introductions and Oδ(1) total rank loss along any path.The bounds apply when each lift’s GAP is proper on a dilate exceeding 2k; rank loss requires deleting all copies of enough types to reduce their span.Source: §9.5 · pp. 81–82

9.6 The algorithm, correctness, and total cost

  • The recursion decides instances correctly on the stated completeness events, with sound positive answers, polynomially many nodes, and only constantly many exceptional transitions per path.Normal boundary steps decrease total array size, while only constantly many steps along a path can enlarge arrays.Source: §9.6 · p. 83
  • The algorithm runs in Oε,c(n + N^1+ε) time with one-sided error.Randomized calls are verified and their failure probabilities are bounded across calls; preprocessing is included in the stated time.Source: §9.6 · p. 85
  • Binary-encoded multiplicities require eO(ℓin) + Oε,c(N^1+ε) bit operations, with the same one-sided error guarantee.The algorithm processes multiplicities as counts rather than expanding copies.Source: §9.6 · p. 85

10 A deterministic algorithm for vector multisets

This section develops a deterministic algorithm for vector sets and multisets with differing coordinate bounds, establishing exact correctness and termination of its recursion before deriving vector-multiset bounds and scalar consequences.

10 A deterministic algorithm for vector multisets

  • The deterministic vector-multiset algorithm handles arbitrary multiplicities and differing coordinate bounds, replacing the randomized subroutines while starting recursion in the original dimension.The reductions preserve the full current vector and respect every multiplicity.Source: §10 · p. 86

10.1 Deterministic sums with bounded cardinality

  • Exact generating functions compute all required bounded corrections deterministically in eO_r(m + kcap^3 vbox) time, where vbox = ∏(∆j + 1).The computation acts directly on multiplicities and retains needed corrections, including cancellations between signed coordinates, without failure probability.Source: §10.1 · pp. 86–87

10.2 Deterministic construction within an ambient interval

  • The common-GAP construction can be made deterministic with unchanged structural conclusions and eOη(mh + h^2hamb) running time.A containing GAP can be constructed in eO_cdbl(uamb + 1) time when |X + X| ≤ cdbl|X|; the exception bounds, available-copy witnesses, filled box, and deletion robustness remain unchanged.Source: §10.2 · pp. 87, 89

10.3 Original vector sums and the dimension bound

  • The vector short-relation invariant bounds current rank below d* and limits each path to fewer than 9d* coordinate introductions and rank-losing deletion events altogether.Here d* = ⌊d(1 + 3/δ)⌋ + 2; total rank lost by deletion on a path is less than 4d*.Source: §10.3 · p. 90

10.4 The recursion, correctness, and running time

  • The deterministic recursion processes boundary corrections using bounded-cardinality supports and interior patches using common GAPs, and is exact and terminating.Boundary processing respects available copies, transfers computed supports to exact target sets, and preserves the geometric allocation bounds; interior decoding recovers the entire old vector.Source: §10.4 · pp. 91–92
  • The recursion terminates: fewer than 9d* exceptional transitions can occur on a path, and normal edges strictly decrease positive integer allocations.The summed allocation over the recursion is e^Od,δ(w0).Source: §10.4 · p. 92
  • Induction through the terminating recursion proves equivalence to the original instance in both directions, preserving capacities, exact targets, and required witnesses.Interior acceptance uses the filled core, unresolved children retain the joint old target and permitted new coordinates, and terminal support computation is exact.Source: §10.4 · p. 92
  • Preprocessing scans the original input once; subsequent recursive work scans distinct types rather than the original n copies.The input is read once on words of Od(log(nν + 2)) bits.Source: §10.4 · pp. 92–93
  • For fixed d and ε>0, vector-multiset subset sum runs in O(n + N^(d+ε)) time; taking Nj=N gives the box bound.The proof also establishes the rectangular bound and d=1 yields Corollary 1.2.Source: §10.4 · p. 93
  • For scalar multisets, deterministic substitutions yield eO(N^(1+4δ)) work after the linear scan; binary-encoded multiplicities give eO(ℓin) + Oε(N^(1+ε)) bit operations.Both forms use the exact residual preprocessing described for the scalar case.Source: §10.4 · p. 93

11 Integer programming and further consequences

This section extends the vector subset-sum result to bounded integer-programming feasibility and further consequences, including prescribed cardinalities, inequalities, discrepancy, and bounded-coefficient objectives. The feasibility reduction uses proximity to limit multiplicities before applying the explicit-copy theorem.

Integer-programming feasibility

  • Proximity restricts the feasible region to a smaller variable box before the explicit-copy theorem is applied, preserving feasibility even with binary-encoded bounds.The section notes that the resulting dependence hidden in O_{d,ε} is not estimated; the conclusion concerns the exponent of N.Source: §11 · p. 94
  • Selecting copies of each column in a multiset is equivalent to choosing bounded integer variables, with at most 2nr listed copies and coordinates bounded by N.The reduction first shifts lower bounds; the target is adjusted accordingly.Source: §11 · p. 94

Prescribed cardinalities

  • A fixed number of prescribed cardinality conditions is handled by adding target coordinates, with only a constant-factor increase in input-box volume.Taking the index set to be all items prescribes subset size; taking sets to be color classes prescribes one count per color.Source: §11 · p. 95

Inequalities and discrepancy

  • Systems mixing equalities and one- or two-sided inequalities retain the coefficient bound N by conversion to equations with bounded slack variables.The conversion adds unit columns and finite variable bounds without adding rows.Source: §11 · p. 95
  • The feasibility corollary also yields exact vector partition and discrepancy-threshold tests, including a partition minimizing the maximum coordinate difference between the two vector sums.The discrepancy test uses binary search over an optimum in [0,nN].Source: §11 · pp. 95–96

Bounded-coefficient objectives

  • Bounded-coefficient linear objectives can be optimized by adding an objective-threshold constraint, with the objective coefficients included in the coefficient bound.The optimization procedure uses binary search and a final feasibility call to recover an optimal vector.Source: §11 · p. 96

12 Scope of the theorem and of the decomposition

The section maps how the paper’s results and proof components fit together, and clarifies which structural claims the decomposition does and does not require.

Scope of results

  • The paper derives bounded integer-programming feasibility from the vector theorem and LP proximity, yielding coefficient-exponent d + ε with a polynomial input-bit-length factor.The result does not claim optimized dependence on dimension.Source: §12 · p. 96

Scope of decomposition

  • The decomposition constructs a common GAP after excluding few items and a chosen subset whose sums fill a box; it does not assume every random sample fills that GAP or require Fourier uniformity.Those stronger structural ideas are described as motivations, not proof assumptions.Source: §12 · p. 96
  • Correctness relies on accepting lifted integer points only through the proved core inclusion and retaining old coordinates and permitted new-coordinate values through recursion.The account also states that processed types preserve their original-copy representation and bounded corrections are computed exactly.Source: §12 · p. 96

A Boolean products and signed color coding

The appendix gives exact Boolean-convolution tools and a signed-budget color-coding construction for retaining subset sums in a bounded box. Its completeness guarantee is simultaneous for a specified finite collection of required sums.

Boolean products

  • Balanced Boolean products compute a sumset by combining supports in a balanced tree, with cost controlled by input size and enclosing array size up to logarithmic factors.The array-size estimate accounts for narrow or zero-width coordinates, and intermediate supports are retained within the same bound.Source: A Boolean products and signed color… · p. 97

Signed color coding

  • For one fixed selection of at most k items, two-stage color coding retains its sum in the budget box with high probability while keeping witnesses on distinct input items.The construction hashes items into buckets, colors within buckets, and combines the resulting supports; its stated guarantee is for a fixed selection.Source: A Boolean products and signed color… · pp. 97–98

Signed-budget lemma

  • The signed-budget lemma partitions items by normalized size and assigns each class a quota, then combines class supports with balanced Boolean products.With failure allowance distributed across classes and required outputs, a union bound gives simultaneous retention of all specified admissible sums.Source: A Boolean products and signed color… · pp. 98–99
  • Computed sums are sound because each class uses distinct items and classes are disjoint; intersections with the budget box only discard sums.For completeness, intermediate sums from an admissible witness stay within the box, so those intersections do not remove its required sums.Source: A Boolean products and signed color… · p. 99

B Lattice boxing and properization

This section collects constructive proofs for tools used in Sections 3 and 4, making explicit the bases, lattice-point counts, and bit costs required by the recursion.

B Lattice boxing and properization

  • The collected constructive proofs make explicit the bases, lattice-point counts, and bit costs required by the recursion.They use standard discrete John, lattice-reduction, and quotient arguments attributed in the main text.Source: B Lattice boxing and properization · p. 99

B.1 Boxing in a basis of the full lattice

The proof boxes a convex body in coordinates induced by a maximum-determinant vertex basis, then uses lattice reduction and residue classes to obtain lattice-point bounds.

B.1 Boxing in a basis of the full lattice

  • A maximum-determinant vertex basis transforms K into K′ contained in [−1, 1]^r, and the resulting coefficient box yields a basis of the entire original lattice.The proof uses symmetry and convexity for the coordinate containment, then transforms back via b_j = A d_j.Source: §B.1 · pp. 99–100
  • LLL reduction and cofactor estimates bound the coordinate widths used to construct the containing coefficient box.The proof establishes lower bounds on coordinate maxima from independent lattice points, giving n_j ≤ 2r_j.Source: §B.1 · pp. 99–100
  • Partitioning lattice points into residue classes gives a dimension-dependent bound on the number of points in a fixed dilation of an origin-symmetric convex body.Within each class, the proof uses an injective map; the resulting factor depends only on dimension and dilation.Source: §B.1 · p. 100
  • The constructions use rational linear algebra, fixed-complexity optimization, and lattice reduction to establish polynomial-time bit bounds.For coordinate boxes, diagonal normalization replaces vertex enumeration.Source: §B.1 · p. 100

B.2 Constructive properization

The constructive properization procedure detects short kernel relations, quotients by them, and boxes the resulting lattice set to produce a proper progression with polynomial-bit implementation.

B.2 Constructive properization

  • Fixed-dimensional integer programming either finds a nonzero kernel relation in 2t · B or certifies none exists, with the certificate implying t-properness.A found relation is made primitive, and the lattice is quotiented by its direction.Source: §B.2 · p. 100
  • The quotient image K is boxed in a basis of the entire quotient lattice, producing an integer GAP containing the original progression.Rounding representatives along the primitive kernel direction bounds the quotient lattice-point count by |(1 + t) · B ∩ Z^r|.Source: §B.2 · p. 100
  • Each detected relation lowers rank, so at most r quotient steps produce the asserted proper progression with polynomial bit length throughout.The cardinality factors accumulated across steps depend only on r and t.Source: §B.2 · p. 100

B.3 Local lattice boxing with an oracle

The section gives a local lattice-boxing construction and details how oracle operations and recursive-instance representations retain polynomial bit costs.

B.3 Local lattice boxing with an oracle

  • Fixed-dimensional convex rounding and lattice reduction produce a box D with M ⊆ D ⊆ γ_d · M and a controlled lattice-point count.The construction uses an ellipsoid E satisfying M ⊆ E ⊆ a_d · M, then bounds box coordinates using reduced-basis geometry.Source: §B.3 · p. 101
  • Rational ellipsoid-based reduction and fixed-dimensional operations implement the boxing construction with polynomial bit cost and output length.The proof avoids requiring an irrational transformation in the implementation.Source: §B.3 · p. 101

C Bit representations and oracle costs

  • The oracle framework uses an O(n)-time hypograph separator for membership and supports fixed-dimensional feasibility and integer-point-or-thin-direction queries.Weighted zonotope queries scan item types rather than individual copies.Source: C Bit representations and oracle costs · p. 102
  • The proof bounds GAP data, fiber geometry, and thin-direction functionals using fixed-dimensional constructions, yielding polynomially bounded coefficients.The GAP construction starts from Oδ(log N)-bit scalar descriptions, and the ambient integer functional retains that bit bound.Source: C Bit representations and oracle costs · pp. 102–103
  • Interior reduction rounds a bounded dual vector to a rational grid, while filtering retained targets preserves all subset-sum solutions and bounds their coordinates.The stated rounded vector has Oδ(log N)-bit entries; retained target coordinates are bounded by O(nw).Source: C Bit representations and oracle costs · p. 103
  • Recomputing lattice bases and scalar maps from current vectors avoids historical matrix products and keeps stored coordinates and maps within Oδ(log N) bits.The proof also bounds item and target coordinates for both set and count representations.Source: C Bit representations and oracle costs · p. 103
Loading 2610.12953v1…