Subset Sum in Almost-Linear Time

1.1 Background

• The main open question is whether Subset Sum admits an eO(n + ∆)-time algorithm, while SETH rules out O(n + ∆^0.99) time.Earlier work had reached eO(n + ∆^1.5) time without distinctness and eO(n + ∆^1.25) when inputs are distinct.Source: §1.1 · p. 4

1.2 Our result

• The result nearly answers the eO(n + ∆) open problem and achieves SETH-optimality up to a subpolynomial factor.The algorithm also finds a witness when one exists for the bounded feasibility problem.Source: §1.2 · p. 4, §1.1 · p. 4
• A deterministic algorithm solves single-constraint bounded integer feasibility in O(n + ∆^1+o(1)) time in the word-RAM model.The problem generalizes Subset Sum; the running time can also be written O(n + Cd∆^1+O(1/d)) for a parameter d.Source: §1.2 · p. 4
• The approach models most inputs through a generalized arithmetic progression, where deep zonotope lattice points correspond to attainable subset sums.The remaining candidates lie in a thin shell, covered by caps; a quotient-space volume measure handles redundancy from the non-injective map, and repeated partitioning controls thin zonotopes.Source: §1.2 · pp. 4–5

1.3 Related work and open questions

• Concurrent work obtained the same theorem, using a more top-down recursive strategy and extending the result to multidimensional Subset Sum.This paper instead groups items and merges answers bottom-up.Source: §1.2 · p. 5
• Improving the algorithm to eO(n + ∆) remains open; computing a compact representation of all attainable sums is another posed question.Bringmann’s algorithm computes all sums in [0,t], and the paper describes their representation as O(∆log(n∆)) arithmetic progressions with a common difference.Source: §1.3 · p. 5

2.1 Geometry of subset sums: random models

• For independent uniform inputs, attainable sums fill a middle interval with high probability, leaving boundary sums to compute in eO(n + ∆) time using Bringmann’s algorithm [Bri17].The filling statement is cited as similar to.Source: §2.1 · p. 6

2.2 Geometry of subset sums: worst-case input

• An algorithmic version of Theorem 2.2 computes GAP P and sets A′ ⊊ Â ⊆ A in eOβ(s²∆) time; combined with Lemma 2.3, this supports filling deep lattice points.For X′ s-generating for H ∩ Z^d, all deep lattice points in Z(X) ⊖ |X′|H map under f to attainable subset sums of Â, provided s ≥ d.Source: §2.2 · pp. 7–8

2.3 Shell volume under idealized assumptions

• Under relative fatness and injectivity, the zonotope boundary shell has volume Oδ(λs∆), and both assumptions are necessary for this bound.The section introduces these as idealized conditions for controlling shell volume.Source: §2.3 · p. 10

2.4 Computing subset sums under idealized assumptions

• Thick shell caps can be handled by transforming each cap to a lattice box, partitioning items by orthant, and convolving partial subset sums in eO_d(|Q ∩ Z^d|) time.A cap covering reduces shell computation to these cap-level problems; Macbeath regions are used to construct coverings.Source: §2.4 · pp. 11–12

2.5 Relaxing the injectivity assumption

• When injectivity fails, the algorithm works in the quotient by the kernel lattice, bounding the quotient shell by Oδ(λs∆) and adapting cap covering and cap computation.Caps are measured in the quotient space, and a cap may be reparameterized into a lower-dimensional box when its Euclidean volume is too large.Source: §2.5 · pp. 12–13

2.6 Relaxing the fatness assumption

• When relative fatness fails, the method computes subset sums for parts separately and restricts the second part to values in [t − W1, t], yielding an Oδ(λs∆) shell bound.This target-based restriction avoids dependence on the much larger |X2| while preserving sums that can contribute to target t.Source: §2.6 · pp. 13–14
• Cap covering restricts each pair of subset sums contributing to a cap to two portions, whose f-values are combined by sparse convolution.The portions are K1∩(xi+Qi−Qi) and K2∩(qi−xi+Qi−Qi).Source: §2.6 · p. 14, Figure 10 · p. 14
• The algorithm forms logarithmically many groups by repeatedly extracting a relatively fat group that reduces the remaining convex hull’s volume by a constant fraction, then merges in reverse order.Repeated CFP embeddings may introduce dimensions or restrict the vectors to a lower-dimensional subspace.Source: §2.6 · pp. 14–15

2.7 Implementation details

• Geometric queries on zonotopes scan their weighted generators, while discretization and the quotient-shell volume bound compensate for the generator-count factor, keeping total time near-linear in that bound.Linear optimization queries extend to modified polytopes through strong separation oracles; Lenstra’s fixed-dimensional algorithm finds a lattice point using a linear optimization oracle.Source: §2.7 · p. 15
• Deep subset sums are found by traversing the zonotope along a fixed lattice vector, and shallow and deep sums are represented as disjoint arithmetic progressions with a common difference.For YES instances, shallow witnesses are recovered directly, while deep witnesses are obtained by solving an LP and applying the rounding argument of Lemma 2.3.Source: §2.7 · p. 15

• Section 3 collects frequently used notations and definitions, while Section 4 states the algorithmic building blocks and shows that they imply Theorem 1.1.Source: Roadmap · p. 15
• Section 5 proves the algorithmic Conlon–Fox–Pham theorem, and Section 6 collects standard optimization and lattice tools.Source: Roadmap · p. 16
• Section 7 partitions input items into groups, while Sections 8 and 9 develop Macbeath-region properties and quotient economic cap covering.Source: Roadmap · p. 16
• Section 10 applies quotient cap covering to group zonotopes, covering shallow subset sums and compactly representing deep ones.Source: Roadmap · p. 16
• Sections 11 and 12 compute each group's subset sums and then merge results across groups.Source: Roadmap · p. 16

• The human authors began the project in 2025 and had a high-level proof framework by June 2026, with some technical details still incomplete.Source: AI Disclosure · p. 16
• The authors' initial inspiration was the AP decomposition and the possibility that the Conlon–Fox–Pham theorem could provide a convexified variant.Source: AI Disclosure · p. 16
• AI assistance was initially limited to literature searches, which brought economic cap covering and Macbeath regions to the authors' attention.Source: AI Disclosure · p. 16
• Since July 2026, ChatGPT interactions helped fill in details and prompted simplifications, including a switch from partition-and-convolve to a simpler shallow-sum method.The authors also report AI input on implementation, preliminary proofs, figures, and proofreading.Source: AI Disclosure · pp. 16–17

3 Preliminaries

• The preliminaries collect frequently used notation and definitions, with less standard notation in displayed equations and definitions in Sections 3.4 and 3.5.Source: §3 · p. 17

3.1 Basic notation

• The basic notation defines [n], assumes Δ≥2, hides parameter-dependent factors, and specifies multiset operations and the distinction between set dilation and repeated sumsets.It also defines eO(T) and eOd(T) as near-linear bounds with polylogarithmic factors.Source: §3.1 · p. 17

3.2 Sparse convolution

• Deterministic nonnegative sparse convolution multiplies bounded-coefficient polynomials in O(t poly log(NU)) time, where t is the product's number of nonzero terms.Consequently, A+B for subsets of [N] can be computed in O(|A+B| poly log N) time.Source: §3.2 · p. 17

3.3 Geometry and lattices

• The geometry preliminaries define convex bodies, zonotopes, lattices, and related operations, and give a bound on quotient-lattice point counts in dilated symmetric convex sets.For s≥1, Lemma 3.2 bounds |πΛ(sK ∩ Γ)| by (2s + 1)^d |πΛ(K ∩ Γ)|.Source: §3.3 · p. 18

3.4 Progressions and s-generating sets

• A progression is defined as f(K ∩ Γ), with properness requiring injectivity on the specified dilation; an s-generating multiset covers a translated sK lattice region by subset sums.A d-generating submultiset X′ ensures that lattice points in Z(X) eroded by |X′|H are subset sums of X.Source: §3.4 · pp. 18–19

3.5 AP decompositions

• An AP decomposition uniquely partitions a finite integer set into maximal arithmetic progressions of a common difference, and its size equals |A \ (A + r)|.The preliminaries also describe a list-based representation and operations for constructing, querying, and restricting decompositions.Source: §3.5 · pp. 19–20

4 Main Algorithm

• A proximity reduction converts the instance to a multiset A with values in [1, ∆] and size O(∆2), in O(n + ∆) time.The algorithm then works on this reduced Subset Sum instance.Source: §4 · p. 20

4.1 Grouping the input integers

• The partitioning theorem divides A into groups and a small exceptional part, embedding each group in a low-dimensional progression with relative fatness and a small generating submultiset.The group conditions support subset-sum computation and include extra conditions useful for merging group answers.Source: §4.1 · p. 20

4.2 Solving one group and merging groups

• OneGroup computes an AP decomposition of a group’s subset sums, while OneGroupWitness recovers a realizing submultiset when given a target.Both run in eO_d(λ|X′|∆) time under the stated O(log ∆)-bit coordinate, multiplicity, and coefficient condition.Source: §4.2 · p. 22
• Merge combines group and accumulated subset sums within a restricted interval, and MergeWitness recovers summands for a target in that interval.The merge is designed so any pair summing into the target interval has its accumulated component within the supplied interval J.Source: §4.2 · p. 22

4.3 Main algorithm

• The main algorithm processes groups from Ak down to A1, restricting partial sums to target-relevant intervals, then combines them with exceptional-part sums computed by dynamic programming.Witness recovery uses backtracing for the exceptional part and the OneGroupWitness and MergeWitness procedures for the groups.Source: §4.3 · pp. 22, 24
• O(n + ∆1+o(1)) total time follows by running parameterized algorithms in parallel and returning the first completed run.The reduction takes O(n + ∆) time; the parallel schedule yields the stated overall bound.Source: §4.3 · p. 24

5 Algorithmic Conlon–Fox–Pham Theorem

• For β > 1 and eligible s, the algorithm finds A′ ⊊ Â ⊆ A and an s-proper, origin-symmetric GAP P of bounded rank containing supp(Â), with |A| − |Â| ≤ Cs log ∆, |A′| ≤ Cs, and A′ s-generating for P.The input is a multiset of nonzero integers in [−∆, ∆], with s in [∆^(1/β), C^−1 min{∆, |A|/log ∆}] ∩ Z.Source: §5 · p. 25

5.1 Preliminaries

• The strengthened algorithmic Freiman lemma supplies a deterministic, origin-symmetric 2-proper GAP of constant rank and O_K(|A|) volume, with a lattice-generation condition, for low-doubling sets.The paper notes that this strengthens the randomized result of [RW24] with determinism, 2-properness, and the lattice-generation condition.Source: §5.1 · p. 26

5.2 Structure of s-fold sumsets

• For s ≥ ∆^(1/β), Lemma 5.5 constructs a bounded-rank GAP P ⊇ A with |sA| ≫β s^d|P| in Oβ(|sA|) polylog(s∆) time.The GAP is origin-symmetric and 2s-proper, and the coordinate images of A generate the integer lattice.Source: §5.2 · p. 26

5.3 Growing subset sums

• A multiplicative drop in the 2s-fold sumset potential bounds the iterative algorithm’s removals by Oβ(s log ∆), while its final batches have many distinct subset sums and generate the GAP’s lattice.The algorithm removes batches of size sℓβ and terminates within uβ log ∆ iterations; each final-iteration batch G(i) satisfies |Σ(G(i))| ≫β |sY0|, and its coordinates generate Zd.Source: §5.3 · pp. 28–30
• The full algorithm runs in Oβ(s |s(supp(A) ∪ {0})| polylog ∆) time, using sparse convolution to evaluate greedy choices and sumsets.The runtime analysis combines Oβ(log ∆) iterations, Oβ(1) greedy calls per iteration, and the final GAP computation.Source: §5.3 · pp. 30–31
• The proof concludes by establishing that A′ is s-generating for P, with the theorem’s constants chosen to satisfy the required bounds.The preceding construction has A′ partitioned into groups and P an origin-symmetric, 2s-proper GAP.Source: §5.3 · p. 31

5.4 Generalization to vectors

• The vector theorem constructs an s-generating subset and an s-proper origin-symmetric GAP of rank at most d, while bounding the removed elements and subset size.For nonzero vectors in (Z∩[−∆, ∆])^k and s in the stated range, |A|−|Â|≤Cs log ∆ and |A′|≤Cs; each GAP width w_j≤C∆, and |sP|≤C|s(supp(Â)∪{0})|. The generalization follows Pham and Zakharov.Source: §5.4 · p. 31

6 Basic Geometric Algorithms

• Rational quantities in the algorithm have bit lengths (log ∆)^O_d(1), making arithmetic-operation costs lower-order factors while allowing bit lengths to be tracked explicitly.The section defines maxbitlen for rationals and extends it to matrices, vectors, maps, polytopes, and lattices.Source: §6 · pp. 31–32

6.1 Linear optimization oracles

• Linear optimization oracles can be built for polytope intersections and linear images, with polynomially controlled query time and bit lengths.The section also gives oracle procedures for convex hulls and zonotopes, and for finding a polytope’s dimension and independent vertices.Source: §6.1 · pp. 32–33

6.2 Polytope approximation

• A constructive barycentric spanner bounds point coefficients by 2 and yields a parallelepiped B and center c with c + B ⊆ K ⊆ c + β_d B.For rational polytopes given by linear optimization oracles, the section computes such B and c with polynomially controlled bit lengths and time.Source: §6.2 · p. 34

6.3 Lattice algorithms

• Lattice procedures compute HNF representations, kernels and images of linear maps, and nearly orthogonal LLL bases, with bit lengths and running times bounded in the input parameters.The section also gives fixed-dimension ILP optimization over lattice points and an enumeration procedure for linear-map values on lattice points in a polytope.Source: §6.3 · pp. 35–36

6.4 Reparameterizing lattices

• A discrete John-type lemma reparameterizes a full-dimensional lattice intersection using a lattice basis and positive integer scales, with a polynomial-time construction for rational inputs.The lemma assumes an origin-symmetric convex body K and a lattice Γ with span(K ∩ Γ) = R^d.Source: §6.4 · p. 36
• The stated running-time bound follows from Lemmas 6.7 and 6.11, while the time and maximum bit-length bounds follow from Lemmas 6.4, 6.10, and 6.15.Source: §6.4 · pp. 37–38
• Lemma 6.16 factors f as g ◦ Φ, maps the lattice to Z^d′, and places ΦK in a box B with |B ∩ Z^d′| ≤ C_d|f(K ∩ Γ)| and g injective on 4B ∩ Z^d′.Here 1 ≤ d′ ≤ d, and C_d depends only on d.Source: §6.4 · p. 37
• The construction reduces dimension by projecting away a subspace in ker f, then reparameterizes the projected lattice with a basis matrix so it becomes Z^d′.The maps are defined so that f = g ◦ Φ and ΦK ⊆ B.Source: §6.4 · p. 38

7.1 Preliminaries

• Lemma 7.1 states that for every s > 0, if K is origin-symmetric, compact and convex, Γ is a lattice with span(K ∩ Γ) = R^d, and dim(U) = d − k, then |sK ∩ Γ ∩ U| ≤ (5d)^d s^−k |sK ∩ Γ|.The cited text also states (c_peel,d |F|)H_Y ⊆ Z_0(F), where c_peel,d ∈ (0, 1) depends only on d, and vol_dim H_Y(conv(±W)) ≤ 1/2 vol_dim H_Y(H_Y).Source: §7.1 · p. 39

7.2 Proof of Theorem 4.2

• Post-processing merges contiguous groups so each group is an Ω_d(1 / log Δ) fraction of the size of its prefix, while the fatness coefficient degrades to O_d(log Δ).The resulting grouping has O_d(log Δ) groups and an extra part of size O_d(s log^2 Δ).Source: §7.2 · pp. 39, 44
• Each iteration embeds remaining vectors in a generalized arithmetic progression, discards O_d(s log Δ) elements to the extra part, and extracts a relatively fat, s-generating group.The algorithmic Conlon–Fox–Pham theorem supplies the progression and a small s-generating submultiset; Lemma 7.2 supplies the relatively fat subset.Source: §7.2 · pp. 39, 40, 41, 43
• The main stage terminates after O_d(log Δ) iterations and takes eO_d(s^2 Δ) total time.The post-processing stage is dominated by the main stage’s running time.Source: §7.2 · pp. 44–45

7.3 Proof of Lemma 7.2

• The proof of Lemma 7.2 repeatedly extracts vertices forming a sufficiently large-volume simplex until the remaining convex hull shrinks, discretizing and bucketing points for running time.It begins by applying Lemma 6.7 to obtain affinely independent points from the convex hull.Source: §7.3 · p. 45
• Each extraction removes the minimum multiplicity of selected vectors from the remaining multiset, and the process runs in near-linear time because each iteration reduces its support.Source: §7.3 · p. 46
• At termination, the boxes containing a maximum-determinant basis form a tuple outside T, implying vold′(conv(±Ŵ)) is at most half vold′(Ĥ).Applying M proves the second claimed property.Source: §7.3 · p. 46

8 Macbeath Regions

• Macbeath regions are convex and centrally symmetric.Source: §8 · p. 46

8.1 Basic properties

• One expansion-containment variant relaxes λ < 1 but requires one region’s center to lie in the other; the quotient variant requires a balanced center.Source: §8.1 · p. 47
• A maximal family of pairwise disjoint quotient images of shrunken Macbeath regions yields the stated covering property under balancedness.Source: §8.1 · p. 48
• Lemma 8.6 gives a modulo-Λ shallow-region property when the specified lattice translate of y avoids K ⊖ D.Source: §8.1 · p. 48

8.2 Finding a balanced center

• The balanced-center construction enlarges a span when it finds a lattice point outside it, and otherwise returns a γ_d-balanced point with the claimed containment.Source: §8.2 · pp. 48–49

8.3 Constructing a cap

• A prescribed interior center admits a cap that approximates its Macbeath region, with the lemma’s containment holding for every t ≥ 1.Source: §8.3 · p. 49

9 Quotient Cap Covering

• O_d(r) caps cover the quotient shell modulo Λ, with total enclosing-parallelepiped volume O_d(ρ) times that of πΛK and a point set R of size O_d(r).Each cap contains a translate of c_dD, the portion outside the caps lies in (K ⊖ D) + Λ, and R + 4dβD ⊆ K.Source: §9 · p. 50

9.1 Preliminaries

• Preliminary geometric lemmas establish quotient-volume subhomogeneity and bound the quotient shell when K contains a translate of ρ^-1D.A separate lemma finds the largest integer t for which a lattice translate of tB, based at a given point, lies within a polytope using an integer linear program.Source: §9.1 · p. 51

9.2 Discretization into cells

• A superlattice discretizes Λ into cells with disjoint interiors that tile a fundamental domain, and an ILP-based procedure finds lexicographic successors among cells meeting K′ modulo Λ.The cell volume is Θ_d(vold(πΛ(B))).Source: §9.2 · p. 53

9.3 Enumerating shallow cells

• O_d(r b_0) iterations suffice to enumerate all shallow cell centers, skipping intervals of deep centers while ensuring no shallow center is missed.The bound follows by grouping skips by their depth scale and bounding their total volume; r = ρ vold(πΛK) / vold(πΛD).Source: §9.3 · pp. 54–55, §9.4 · p. 56

9.4 Constructing a quotient Macbeath net

• Balanced centers covering the shallow cells are selected, then an inclusion-maximal subcollection is chosen whose half-scaled Macbeath regions are disjoint modulo 2qΛ.The covering after enlargement follows from balancedness, while packing bounds the total volume.Source: §9.4 · pp. 55, 57
• The packing-volume bound yields |Y| ≤ Od(r) for the quotient Macbeath net.The volume bound combines with B0 ⊆ αMy for all y ∈ Y.Source: §9.4 · p. 57
• A greedy algorithm builds an inclusion-maximal disjoint collection by selecting candidate centers and removing candidates that intersect the selected center’s neighborhood.It enumerates nearby quotient cells and tests the remaining candidates associated with those cells.Source: §9.4 · p. 58

9.5 Completing the proof

• For each y ∈ Y, shrinking toward c maps y to z_y = c + (1 + 2θ)^−1(y − c) ∈ K, with M_1^K(z_y) − z_y = (1 + 2θ)^−1 M_y.Source: §9.5 · p. 59
• Under the condition Py − zy ⊆ (4d + 3)mβMy, Lemma 9.2 gives vold(πΛPy) ≤ Od(vold(πΛMy)), bounding the projected volume of Py by Od times that of My.Source: §9.5 · p. 59
• The construction enumerates Od(r) points and retains r only when r + 2B0 ⊆ K, yielding centers that cover the specified union within D + Λ.For every x in the union of Py + D + Λ, a returned center lies in x + D + Λ.Source: §9.5 · p. 60

10 Cap Covering for Subset Sums

• The cap-covering approach represents sufficiently deep lattice points as attainable subset sums and covers the remaining shallow subset sums with caps.It applies to the zonotope of vectors representing input integers in a proper progression, assuming a small generating submultiset.Source: §10 · p. 60
• Theorem 10.1 returns an AP decomposition G of size O_d(ρ(u − ℓ)) and caps with enclosing parallelepipeds under its stated progression, generating, and thickness assumptions.The caps satisfy the theorem’s volume and thickness bounds; the construction has bit complexity bounded in terms of the input bit length.Source: §10 · p. 60

10.1 Proof of Theorem 10.1

• The proof approximates the unknown thickness parameter ρ using a parallelepiped B, with ρ′ ≤ βρ, before applying quotient cap covering.It obtains P with P ⊆ (K − K)/2 ⊆ βP, then sets B = βρ′P.Source: §10.1 · pp. 61–62
• The proof constructs G by combining the f-values outside E with S, yielding G ⊆ f((K ⊖ D′) ∩ Γ) ⊆ f((K ⊖ D) ∩ Γ).It identifies bounded gaps in f(K ∩ Γ) \ E by whether their first values belong to S.Source: §10.1 · p. 63
• Theorem 10.1’s construction runs in near-linear time in ρ(u − ℓ), up to dimension-dependent polylogarithmic factors, and produces an AP decomposition of the claimed output size.The proof bounds |E| + |S| by O_d(ρ′w), then uses ρ′ ≤ βρ and w ≤ u − ℓ.Source: §10.1 · pp. 63–64

10.2 Witness recovery

• Witness recovery reduces the target to finding a subset sum from X \ X′ and a matching sum from X′, using LP rounding and sparse convolution.The sparse-convolution step finds the witness for f(y − z′) ∈ Σ(f(X′)) in eO(R) time.Source: §10.2 · pp. 64–65

11.1 Computing subset sums in a cap

• For a cap Q, Lemma 11.1 computes a set containing the mapped subset sums in Q and supports recovery of a witnessing submultiset.The proof reduces to multidimensional Subset Sum; an enclosing parallelepiped is given as input.Source: §11.1 · p. 65
• The cap computation boxes the instance, partitions vectors by coordinate-sign pattern, and combines the resulting sets using sparse convolution.Nonnegative cap direction values allow vectors outside the cap to be removed; the proof establishes the returned set’s containment in both directions.Source: §11.1 · p. 66

11.2 Proof of Lemma 4.3

• The cap-covering construction runs in eO_d(sλΔ) time and returns an arithmetic-progression decomposition of size O_d(sλΔ).It combines the cap covering theorem with the cap-subset-sum lemma.Source: §11.2 · pp. 66–67

12 Merging Groups

• Cap covering supplies deep sums and caps for shallow sums, which identify useful summand pairs for sparse convolution.The procedure forms candidate summand lists for each cap, intersects them with the input sumsets, and convolves the resulting pairs.Source: §12 · pp. 67–68
• For a shallow sum outside G, the cap-covering claim places its two summands in corresponding candidate lists, so their sum is included in a computed T_i.Together with G, these sets recover the desired sumset on interval I.Source: §12 · pp. 68–69
• The total time for the merging construction is ρ|J+|(log Δ)^O_d(1).The resulting answer set has an arithmetic-progression decomposition of the same common difference and size O_d(ρ|J+|).Source: §12 · p. 69

A Proof of Lemma 5.3

• The extension adds 2-properness and generation of Z^d to the algorithmic Freiman theorem of Randolph and Węgrzycki [RW24].The proof also describes the extension as a derandomization of their modeling step.Source: A Proof of Lemma 5.3 · p. 70
• Conditional expectations fixes the bits of λ so that no nonzero element of Adiff maps to a multiple of m.The proof computes conditional expectations for both choices of each next bit; after all bits are fixed, N(λ)=0.Source: A Proof of Lemma 5.3 · p. 71
• The construction returns an origin-symmetric, 2-proper GAP of rank O_K(1) and volume O_K(|A|).The GAP contains A+A, and the construction takes O_K(|A|) polylog Δ time.Source: A Proof of Lemma 5.3 · p. 72

B Proof of Theorem 5.13

• The proof reduces Theorem 5.13 to Theorem 5.1 by encoding vectors as integers.It applies Theorem 5.1 with exponent β0=2βk.Source: B Proof of Theorem 5.13 · p. 72
• The lifted GAP P is s-proper, contains the represented input support, and has an s-generating subset.These properties follow by transferring the corresponding properties through the encoding map.Source: B Proof of Theorem 5.13 · pp. 72–73
• The selected subsets satisfy |A′|≤Cs and |A|−|Â|≤Cs log Δ.The constant C depends on β and k.Source: B Proof of Theorem 5.13 · p. 73

• Binary bundling replaces repeated vectors with logarithmically many weighted copies while preserving every attainable multiplicity.The resulting equivalent instance has size eO_d(|B ∩ Z^d|).Source: C Proof of Lemma 11.2 · p. 73
• Distinct fixed primes and powers q_j at least d(t_j + 1) are used to define the integer encoding E and bound H = E(t).Source: C Proof of Lemma 11.2 · p. 73
• The encoding is linear and maps bounded vector subset sums into integer subset sums in [0, H], with at most one nonnegative vector decoding to each integer in that range.Pairwise coprimality of the q_j uniquely determines each coordinate from the encoded value.Source: C Proof of Lemma 11.2 · p. 73
• Chan’s deterministic all-targets algorithm computes the encoded subset sums in eO(n + H) time, after which inversion recovers vector sums and a witnessing submultiset.Source: C Proof of Lemma 11.2 · pp. 73–74

• An arithmetic-progression decomposition has size |S \ (S + s)| for common difference s, and some a in supp A gives Σ(A) a decomposition of size at most |Σ(A)| ln|Σ(A)|.Source: D AP Decompositions of All Subset Sums · p. 74
• For n items drawn from [1, ∆], Σ(A) has an arithmetic-progression decomposition of size O(∆log(n∆)).Source: D AP Decompositions of All Subset Sums · p. 74
• Near-linear computation of a full decomposition remains open; the paper’s algorithm loses information about full Σ(A) when combining group answers over shorter intervals.Source: D AP Decompositions of All Subset Sums · p. 74
• Submultiplicativity and averaging yield an item a whose shift overlaps Σ(A) enough to give the stated decomposition-size bound.The proof bounds |S ∩ (S + a_i)| below by |S_i|, so the decomposition size is at most |S| − |S_i|.Source: D AP Decompositions of All Subset Sums · p. 74
• A T(n, ∆)-time decomposition algorithm would solve Bounded Support Subset Sum in eO(T(n, 3t√n) + n + t√n) time, or eO(n + t√n) if T(n, ∆) ≤ eO(n).This addresses Węgrzycki’s question about an O(n^(1−δ)t + n^O(1))-time algorithm for some δ > 0.Source: D AP Decompositions of All Subset Sums · pp. 74–75
• For large items, fewer than K = ⌈√n⌉ can appear in a subset summing to at most t; encoding each as Ka_i + 1 lets subset sums recover the cardinality array L.The resulting subset-sum computation takes eO(n + t/K) time.Source: D AP Decompositions of All Subset Sums · p. 75
• For small items, encoding each as 2na_i + 1 makes sums and cardinalities recoverable, and an AP decomposition supports offline predecessor queries for the array S.The queries use the decomposition’s progression endpoints and active residues modulo its common difference.Source: D AP Decompositions of All Subset Sums · p. 75