PaperlayerView exact revision on arXiv

Source-linked AI summary

Pigeonhole Equal Subset Sum: Subexponential Algorithm, Tight Lower Bounds, and Average-Case Analysis

Deepak Bhati, Pranjal Dutta, Antoine Joux, Mahesh Sreekumar Rajasree, Karol Wegrzycki

arXiv:2610.31056v1cs.DS

TL;DR

Pigeonhole Equal Subset Sum asks whether a collision can be found efficiently, and the paper addresses open questions about subexponential algorithms and improving the M^1/3 barrier. It develops a density-dependent PESS algorithm and uses two-level filtering for average-case variants, reporting improved running times and a conditional lattice-based lower bound.

  • Problem

    PESS asks whether equal-sum subsets can be found in subexponential time and whether the O⋆(M^1/3) barrier can be improved.

    Source: §1 · p. 1, §8 · p. 47

  • Method

    For average-case variants, the paper partitions inputs into four blocks and filters subset sums through two rounds of merging, modulo p and then q.

    Source: §2.3 · p. 8

  • Results

    Theorem 1.1 improves O⋆(M^1/3) when δ > 19, and average-case techniques improve the state of the art for δ ≥1.

    Source: §1.1 · p. 3

  • Takeaways & Limitations

    The paper makes partial progress on both open questions: subexponential PESS algorithms and improving the O⋆(M^1/3) barrier.

    Source: §1.1 · p. 3, §8 · p. 47

    The lower bound is conditional on Hypothesis 1, a lattice-problem hardness assumption that the paper says is not standard.

    Source: §1.1 · p. 3

Abstract

from arXiv · show

The Equal Subset Sum problem asks, given n positive integers bounded by M, to find two distinct non-empty subsets with the same sum. We study this problem in the regime $M = 2^{o(n)}$, where the pigeonhole principle guarantees that a solution exists, and the main challenge is to find one efficiently. A straightforward dynamic-programming algorithm runs in time poly(n).$M$. After a sequence of improvements, the current best algorithm, due to Jin, Williams, and Zhang (ESA 2025), achieves running time poly(n).$M^{1/3}$. In this work, we give the first poly(n).$M^{o(1)}$-time algorithm for Equal Subset Sum in the regime $M = 2^{o(n)}$. We complement this algorithmic result with a tight conditional lower bound showing that any substantial improvement would require a major breakthrough in approximation algorithms for lattice problems, building on recent techniques of Vafa and Vaikuntanathan (STOC 2025). Finally, we show that our techniques yield an asymptotically faster algorithm for the regime when $M = \Theta(2^{n})$: a poly(n)$\cdot 2^{n/4}$-time algorithm in the average case.

1 Introduction

Pigeonhole Equal Subset Sum asks for distinct subsets with equal sums, and the paper studies how efficiently to find such collisions. It gives a density-dependent algorithm, conditional lower bounds, and faster average-case algorithms.

1 Introduction

  • PESS is total in the pigeonhole regime: there are 2^n − 1 non-empty subsets but only 2^n − 2 possible nonzero sums.The paper uses M for the bound on the integers in its instances.Source: §1 · p. 2
  • The motivating open question asks whether PESS admits a subexponential-time algorithm [Jin24, JW24].The paper also notes prior running-time improvements culminating in O⋆(M^1/3).Source: §1 · p. 2

1.1 Our Results

  • poly(n)·M^o(1) time suffices when M = 2^o(n), by a corollary of the paper’s PESS algorithm.Theorem 1.1 gives a deterministic algorithm with runtime poly(n)·M^O(1/log δ), where δ = n/log M.Source: §1.1 · p. 2
  • Theorem 1.1 improves on the O⋆(M^1/3) algorithm of Jin, Williams, and Zhang when δ > 19.The paper says this does not fully resolve the open question of improving the M^1/3 barrier.Source: §1 · p. 2, §1.1 · p. 3
  • Under Hypothesis 1, no 2^o(n/log n)-time PESS algorithm exists, nor a poly(n)·M^o(1/log n)-time algorithm, even for δ = n^1/2+o(1).Theorem 1.2 is conditioned on a lattice-problem hardness assumption.Source: §1.1 · p. 3
  • O⋆(M^1/4)-time algorithms are presented for average-case Equal Subset Sum when M ≤ 2^n.The average-case setting requires correctness on most inputs rather than every input.Source: §1.1 · p. 3

2 Our Techniques

The technique combines dynamic programming with Karmarkar–Karp differencing to find equal-sum subsets deterministically, even in the worst case. It also uses repeated block merging and pruning to retain large collections of sums that agree on low-order bits.

2.1 Technique behind Theorem 1.1

  • Enumerating subsets until a collision appears gives a straightforward poly(n) · M-time algorithm, since a collision must occur within the first M nonzero sums.Source: §2.1 · p. 4
  • Repeatedly pairing sorted input numbers and keeping pairs with gaps at most 4M/n leaves at least n/4 good pairs in each round.The process repeats for Θ(log n) rounds, shrinking values until it must encounter zero.Source: §2.1 · p. 5
  • A zero produced by differencing encodes two distinct equal-sum subsets because the final difference’s sign assigns its paired element to one subset or the other.Source: §2.1 · p. 5
  • Combining dynamic programming with Karmarkar–Karp differencing yields a deterministic algorithm that works in the worst case.The differencing strategy is adapted from partitioning to Equal Subset Sum.Source: §2.1 · p. 5
  • The algorithm partitions inputs into blocks, merges their sumsets by low-order residues modulo W^j, and prunes each merge to W representatives from its largest residue class.The initial lists contain subset sums within each block; keeping large collections with matching low-order bits is the pruning objective.Source: §2.1 · p. 5
  • The simplified analysis ignores that n decreases at each iteration, a change that contributes only a low-order factor.Source: §2.1 · p. 5

11 end

This section presents the collision-based lattice reduction and filtering and moment-analysis techniques behind the conditional PESS lower bound and Theorems 1.3 and 1.4, along with the recursive algorithm’s running time and collision guarantee. It also reviews connections between Equal Subset Sum, Subset Sum variants, and lattice problems, as well as average-case algorithms for related problems.

11 end

  • The recursive algorithm runs in poly(n)·M^o(1) time for sufficiently large k and must detect a collision by level log k.Its per-level transitions take quadratic time; the proof uses maintained set invariants and the choice of W and k to force equal sums.Source: §11 · p. 6

2.2 Techniques behind Theorem 1.2

  • A hypothetical fast PESS algorithm would yield a 2^O(εn)-time algorithm for approximate SIVP, contradicting Hypothesis 1; the reduction is worst-case and assumes subexponential hardness stronger than.It samples lattice vectors, encodes them as positive integers, and decodes an equal-sum collision into a short lattice vector; the reduction ensures a nonzero output with constant probability.Source: §2.2 · pp. 7–8

2.3 Techniques behind Theorem 1.3 and Theorem 1.4

  • Theorem 1.3 and Theorem 1.4 use two-level filtering: four blocks of subset sums are merged modulo p and q, while integer collisions additionally require analyzing carries and remaining bits.The modular case uses CRT and uniform distributions; integer collision analysis is more intricate, including at the first-moment stage.Source: §2.3 · pp. 8, 10
  • To establish success probability, the analysis controls the collision count’s second moment, using the more tractable modular variable to bound the integer case.For the modular second moment, it partitions vector quadruples into cells with uniform bounds on joint probabilities and cell sizes; it uses an algebraic approach rather than exponential sums.Source: §2.3 · p. 11
  • The filtering analysis gives an expected final-list size of 2^n/4 and is presented as the first fine-grained average-case analysis for density-1 Equal Subset Sum combining two-round Wagner-style pruning with an explicit second-moment argument.The authors conjecture that randomized bin choices may improve success probability to 1−o(1), and that the viewpoint may extend to worst-case inputs with structural ideas from Jin and Wu.Source: §2.3 · p. 12

2.4 Related Work

  • Hoberg et al. imply that polynomial-time Equal Subset Sum when the integer sum is 2^n−√n yields a polynomial-time approximation to Shortest Vector.Their result connects Number Balancing to Minkowski’s vector problem; Ajtai showed that an O(√n)-approximation to Minkowski’s vector problem yields an O(n)-approximation to Shortest Vector.Source: §2.4 · p. 12
  • Average-case Subset Sum work includes a polynomial-time algorithm for low-density inputs and subsequent developments with cryptographic implications; recent work also addresses average-case low-density k-XOR.Lagarias and Odlyzko gave the low-density result; subsequent work includes, and Agrawal et al. studied low-density average-case k-XOR.Source: §2.4 · p. 12
  • Prior work reduces Equal Sum and other Subset Sum variants to CVP, Bounded Distance Decoding, or gap Shortest Vector.The cited reductions include van Emde Boas for Equal Sum; Micciancio for ordinary Subset Sum; Krishnamoorthy, Webb, and Moyer for decisional Number Partitioning; Yu and Xiao for multidimensional modular Subset Sum; Dutta and Rajasree for Unbounded Subset Sum under ℓ1 and ℓ∞ norms; and Hittmeir [Hit25] for constrained Subset Sum.Source: §2.4 · p. 12

3 Preliminaries

The preliminaries establish notation and define the lattice problems used in the paper’s hardness discussion. They state the lattice hardness hypotheses and disclose the limited use of AI tools in the arXiv version.

3 Preliminaries

  • The notation fixes logarithms as base 2, defines [n] and subset sums, and specifies vector and matrix norms.The preliminaries also state the Prime Number Theorem.Source: §3 · pp. 12–13

3.1 Lattices

  • A lattice is generated by linearly independent integer combinations of basis vectors; SVP seeks its shortest nonzero vector, while SIVP and nSMP use the nth successive minimum.The paper assumes the ℓ2 norm unless stated otherwise; SIVP asks for n independent vectors, whereas nSMP asks for one vector.Source: §3.1 · p. 13

3.2 Hardness Hypothesis

  • The hardness discussion states that no 2^(O(n/ℓ))^(1−ε)-time algorithm solves the specified approximate SIVP task, and proposes a stronger hypothesis excluding 2^(εn)-time polynomial-approximation algorithms for nSMP.The authors note that refuting their hypothesis would constitute a significant breakthrough in approximate SVP.Source: §3.2 · p. 14

3.3 Declaration on the Use of AI Tools.

  • For the arXiv version, Claude (Opus) was used only for proofreading, language editing, and identifying potential inconsistencies; the authors say the technical contributions are original and independently verified.The submitted FOCS 2026 version used no AI tools.Source: §3.3 · p. 14

4 Subexponential algorithm: Proof of Theorem 1.1

The section proves a deterministic algorithm for PESS with running time poly(n) · M^O(1/log δ), where δ is the instance density. It builds and filters subset-sum lists so that, if no collision is detected earlier, the final list forces two equal sums.

4 Subexponential algorithm: Proof of Theorem 1.1

  • poly(n) · M^O(1/log δ) time suffices to find two distinct equal-sum subsets when nM < 2^n − 1, with δ = n/log M.The result is deterministic.Source: §4 · p. 14
  • For M = 2^o(n), the algorithm runs in poly(n) · M^o(1) time.This follows as a corollary of Theorem 1.1.Source: §4 · p. 14
  • The algorithm chooses the largest power-of-two k satisfying nM ≤ 2^⌊n/k⌋ log k, sets W = 2^⌊n/k⌋, and partitions the input into k blocks of size ⌊n/k⌋.If such a k does not exist, the text says δ = Ω(1) and brute force suffices; one leftover block is ignored.Source: §4 · p. 14
  • At each merging level, the algorithm groups candidate sums by residues modulo increasing powers of W and retains a largest residue class, returning immediately if it finds a collision.The initial lists are constructed from the block subsets, and stored subsets allow a sum collision to be returned as two input subsets.Source: §4 · p. 15
  • Each maintained list has size at most W, and computing the sets takes poly(n) · W^2 time.This bounds the algorithm’s running time as used in the proof of Theorem 1.1.Source: §4 · p. 15
  • The argument shows that if no collision was detected, congruent values a and b bounded by n·M ≤ 2⌊n/k⌋log k ≤ W log k must be equal, contradicting that assumption.Source: §4 · p. 16

5 Conditional Lowerbound: Proof of Theorem 1.2

The section reduces lattice-vector finding to Pigeonhole Equal Subset Sum (PESS) by encoding sampled lattice points as positive integers and recovering a lattice vector from an equal-sum collision. Under Hypothesis 1, it uses this reduction to establish two conditional lower bounds for Equal Subset Sum, with polynomially many repetitions making failure probability negligible.

5.1 Construction

  • A reduction samples lattice points, encodes them as positive integers, and converts a PESS collision into a candidate lattice vector.It computes a short basis, uses discrete-Gaussian samples, and returns the shortest nonzero vector among candidates.Source: §5.1 · pp. 16, 18
  • The lattice-sample procedure runs in N · poly(n, bitlength(B), log(s)) time.It outputs N independent samples from a discrete Gaussian; the reduction sets s := 4π√n N ∥D∥2.Source: §5.1 · p. 17

5.2 Correctness

  • The encoding yields a valid strong-regime PESS instance and a lattice vector of norm at most N^5 · λn(L), while the correctness analysis establishes nonzeroness with constant probability.For sufficiently large n, the encoded integers satisfy M ≤ 2^o(N); the norm bound holds conditioned on all sampled vectors meeting the stated ℓ∞ bound.Source: §5.2 · pp. 19–21
  • Conditioned on the good event, the modified reduction outputs a nonzero vector with probability at least 1/2; independent polynomially many repetitions make the original reduction’s failure probability negligible.The stated conclusion assumes PESSerr is negligible or smaller than 1/2−1/poly(n).Source: §5.2 · pp. 23–24

5.3 Proof of Theorem 1.2

  • Under Hypothesis 1, no algorithm can solve Equal Subset Sum on N-element subsets of {1, …, M} with probability >3/4 in time poly(N)·M^(ε/log N), for some ε > 0.The lemma also states this bound for M = 2^Θ(…).Source: §5.3 · p. 24
  • The reduction turns a faster Equal Subset Sum oracle into a lattice algorithm running in O(2^(δH·n)) and returning a nonzero vector of norm at most n^10λ_n(L), contradicting Hypothesis 1.Source: §5.3 · p. 25
  • Under Hypothesis 1, no algorithm can solve Equal Subset Sum on N-element subsets of {1, …, 2^N−1} with probability >3/4 in time O(2^(εN/log N)), for some ε > 0.Source: §5.3 · p. 25
  • For the second tradeoff, the reduction returns a nonzero lattice vector of norm at most n^6λ_n(L) in O(2^(δH·n)) time, again contradicting Hypothesis 1.Source: §5.3 · p. 25

6 Modular average-case: Proof of Theorem 1.4

This section analyzes the average-case performance of filtering algorithms for random modular Equal Subset Sum instances, using collision counts and moment bounds. It establishes an expected running time of O⋆(M^(1/4)) for Algorithm 3 and an Ω(1) fraction of instances on which filtering finds a collision in O⋆(2^(n/4)) time.

6 Modular average-case: Proof of Theorem 1.4

  • The analysis targets ACM-RESS on uniformly random inputs modulo M; the presentation treats M = Θ(2^n), while broader moduli trade off against success probability.The passage states that average-case algorithms also work for M ≤ poly(n) · 2^n, with success probability depending on the choice of parameters.Source: §6 · pp. 25–26

6.1 Success Probability

  • Algorithm 3 succeeds exactly when its final filtered list contains at least one non-trivial modular collision, counted by C.The analysis therefore reduces the algorithm’s success probability to P(C > 0).Source: §6.1 · p. 27

6.1.1 First Moment

  • The first-moment analysis uses independence among the CRT components a(p), a(q), and a(r), and among events tied to distinct binary vectors.The first-moment calculation is used as part of the proof of the success-probability bound.Source: §6.1.1 · pp. 28–29

6.1.2 Second Moment

  • To control second-moment dependencies, the proof partitions vector quadruples by matrix ranks, bounding both cell sizes and joint event probabilities.For the ranked matrices, the joint probability is bounded by 1/(p^t1 · p^t2 · q^t3).Source: §6.1.2 · pp. 30–31
  • For odd r, distinct difference vectors not congruent up to sign collide modulo r with probability 1/r^2; for general r, the bound is 1/r^2 or 2/r^2.Source: §6.1.2 · p. 30
  • The second-moment bounds also use the estimate |T_m| < 6^m for the specified related vector quadruples.Source: §6.1.2 · p. 32
  • Combining equations (4), (5), and (6), the second-moment analysis obtains an O(1) bound.This completes the proof of Lemma 6.0.3.Source: §6.1.2 · p. 33

6.1.3 Concentration

  • The concentration argument applies Paley-Zygmund to C with θ = 0 to establish concentration around its mean.The passage identifies this as the proof of Lemma 6.0.1.Source: §6.1.3 · pp. 33–34

6.2 Complexity Analysis

  • Algorithm 3 runs in expected time O⋆(M^(1/4)) over random inputs, with a stated tail bound; filtering succeeds with a collision on an Ω(1) fraction of instances in O⋆(2^(n/4)) time.The final list has a collision for that fraction of instances.Source: §6.2 · pp. 34–35

7 Integer average-case: Proof of Theorem 1.3

This section analyzes Algorithm 4 on average-case integer inputs, adapting modular filtering to account for carry propagation and remaining high-order bits. It establishes an expected running time of poly(n)M^1/4 and a tail bound using moment estimates, local-limit arguments, and concentration.

7 Integer average-case: Proof of Theorem 1.3

  • ACI-RESS samples n integers uniformly from [M] and seeks distinct nonempty binary vectors with equal integer dot products, for n and M divisible by 4 and M ≤ 2^n.Source: §7 · p. 35
  • The integer algorithm retains the modular-case approach, but after agreement modulo pq its analysis must handle carry propagation and collision over the remaining high-order bits.The passage identifies this carry-and-bits analysis as the bottleneck in the integer case.Source: §7 · p. 35

7.1 Success Probability

  • Success is characterized by at least one surviving integer collision, analyzed through the first and second moments of the collision count.Source: §7.1 · pp. 37–38

7.1.1 First Moment

  • The first-moment analysis reduces overlapping vector pairs to non-overlapping supports, then counts pairs whose non-overlapping components have Θ(n) weight on both halves for the Local Central Limit Theorem.Shared 1-coordinates contribute equally to both sums, so the argument focuses on the remaining components.Source: §7.1.1 · pp. 39–41
  • The first-moment argument constructs a set T of Θ(4^n) pairs whose auxiliary binary vectors satisfy the stated constraints.The excerpt does not include the constraints themselves.Source: §7.1.1 · pp. 41–42

7.1.2 Second Moment

  • The second-moment analysis bounds C(int) by relating it to modular collisions and applying the modular-case computation under asymptotic uniformity of the residues.The passage states the resulting bound is the desired one but does not supply its formula.Source: §7.1.2 · pp. 42–43

7.1.3 Concentration

  • Paley–Zygmund concentration, together with Lemmas 7.0.2 and 7.0.4, yields the stated success probability for Algorithm 4.The supplied passage does not give the probability’s value.Source: §7.1.3 · p. 43

7.2 Complexity Analysis

  • Algorithm 4 runs in expected time poly(n)M^1/4 over random inputs and also satisfies a tail bound.The supplied passage states the tail bound exists but does not include its form.Source: §7.2 · p. 43

7.3 Distribution of the sum of Integer random Variables

  • The local central limit theorem approximates sums of bounded i.i.d. integer variables, while the analysis shows three relevant events are asymptotically independent under the stated weight conditions.For central sums, the carry bits approach a discrete normal distribution with mean w_i/2 and variance Θ(w_i); the total sum modulo pq and left sum modulo p approach uniformity conditional on the carry bits.Source: §7.3 · pp. 44–45

7.3.1 Proof of Proposition 7.0.1

  • The proposition proof uses intersections of Gaussian central windows, each containing Θ(√n) points, and the local limit theorem to establish its two stated parts.The excerpts do not specify the proposition’s underlying probability bounds.Source: §7.3.1 · p. 46

8 Conclusion and Future Directions

The paper advances Pigeonhole Equal Subset Sum with a density-dependent algorithm, a conditional lower bound, and average-case algorithms for M = Θ(2^n). It leaves open whether the remaining gap to a 2^o(n)-time algorithm can be closed and whether the average-case result extends to worst case.

8 Conclusion and Future Directions

  • The cited passage states a deterministic algorithm with running time poly(n) · M^{O(1/log δ)}, where δ = n/log M; it provides no further supported conditions or comparative result.Source: §8 · p. 47
  • Theorem 1.2 gives a conditional lower bound matching the algorithm’s running-time dependence for polynomial δ, based on lattice-problem hardness.The paper also rules out a 2^o(n/log n)-time algorithm for PESS conditionally, leaving a log n factor in the exponent relative to the open question.Source: §8 · p. 47
  • Theorem 1.3 and Theorem 1.4 give average-case O*(2^{n/4})-time algorithms when M = Θ(2^n).The result is part of the paper’s effort to improve the state of the art in the average-case regime.Source: §8 · p. 47
  • The paper leaves closing the gap to a 2^o(n)-time PESS algorithm as a major open challenge.Its lower bound is tight only for exponential running times and does not improve the polynomial-time lower bound of Vafa and Vaikuntanathan.Source: §8 · p. 47
  • The authors ask whether the average-case algorithm for density δ = 1 can be extended to worst case and whether its 1/4 exponent can be improved.They conjecture that combining their average-case analysis with structural insights of Jin, Williams, and Zhang could yield an O*(2^{n/4})-time worst-case algorithm.Source: §8 · p. 47

A Sampling Lattice Points

This section establishes a discrete-Gaussian sampler for lattice points and bounds the size of its outputs. It also records a shift-distance estimate used in the proof.

A Sampling Lattice Points

  • The section defines the smoothing parameter ηϵ(L) through the dual lattice and gives the basis-dependent upper bound ηϵ(L) ≤ 2B√n for ϵ = 2^-n.Here B denotes the basis norm in the cited theorem.Source: A Sampling Lattice Points · p. 48
  • For a full-rank lattice with basis B and s ≥ 4π√n ∥B∥2, the theorem gives N ≥ 2 independent samples from the discrete Gaussian in time N · poly(n, bitlength(B), log(s)).Except with probability at most 2^-n, all samples lie in L ∩ Ball∞(0, R).Source: A Sampling Lattice Points · p. 48
  • The sampler independently draws each output from the discrete Gaussian DL,s over L using the basis-sampling algorithm.The cited sampling procedure runs in poly(n, bitlength(B), log s) time per sample and produces a distribution negligibly close to DL,s,c.Source: A Sampling Lattice Points · p. 48
  • A discrete-Gaussian tail bound and a union bound show that all N samples lie in the stated ℓ∞ ball except with negligible probability.The theorem gives the explicit failure bound 2^-n.Source: A Sampling Lattice Points · pp. 48–49
  • For a shortest nonzero lattice vector v*, the proof bounds the statistical distance between DL,s and its translate using Pinsker’s inequality.It uses invariance of the Gaussian lattice sum under translation and symmetry of DL,s in the subsequent calculation.Source: A Sampling Lattice Points · p. 49

B Proof of Theorem 5.1

The proof builds a lattice basis by iteratively finding short vectors in projected lattices and reducing their lifts. The resulting basis has a norm bound derived from successive minima and approximate SVP.

B Proof of Theorem 5.1

  • For any κ > 0, Theorem 5.1 computes a basis D in O(2^{Cn/κ}) time with ∥D∥2 ≤ C · n^κ · λn(L), for a constant C > 0.The basis norm is the maximum Euclidean norm of its basis vectors.Source: B Proof of Theorem 5.1 · p. 49
  • The reduction converts a γ(n)-approximate SVP oracle into a √nγ(n)-approximate SIVP algorithm using n oracle calls.The cited approximate SVP algorithm runs in 2^{O(n/κ)} time and returns an n^κ-approximation.Source: B Proof of Theorem 5.1 · pp. 50–51
  • The proof constructs basis vectors iteratively by projecting onto the orthogonal complement of the vectors already chosen and querying an approximate SVP oracle on the projected lattice.It lifts each nonzero projected vector to L and size-reduces the lift against the existing basis vectors.Source: B Proof of Theorem 5.1 · p. 50
  • Each new vector remains independent of its predecessors because its projection is nonzero, and its Gram–Schmidt vector equals that projection.Size reduction keeps the Gram–Schmidt coefficients bounded as described in the proof.Source: B Proof of Theorem 5.1 · p. 50
  • The projected-lattice oracle vector is bounded using the nth successive minimum: among n independent vectors of norm at most λn(L), at least one has a nonzero projection.The oracle guarantee and monotonicity of γ are then used to obtain the bound.Source: B Proof of Theorem 5.1 · p. 50

B.1 Variant of Theorem B.1 for n-SMP

The n-SMP variant preserves the polynomial-time lattice reduction with n oracle calls, while adapting the projected-lattice bound used in the proof. The projected vectors retain enough independent short vectors to bound the oracle output.

B.1 Variant of Theorem B.1 for n-SMP

  • The reduction makes n oracle calls and outputs n linearly independent vectors in the input lattice.It obtains the vectors using an oracle that returns a nonzero vector from each rank-m lattice queried.Source: §B.1 · p. 51
  • At iteration i, projection onto the orthogonal complement of the previously constructed vectors gives a lattice of rank m = n − i + 1.The oracle is applied to this projected lattice.Source: §B.1 · p. 51
  • The proof modifies only the bound on the oracle output for the projected lattice; the size-reduction step still gives |µ_i,j| ≤ 1/2.The construction of each b_i from a lift of the oracle vector is unchanged.Source: §B.1 · pp. 51–52
  • At least m projected vectors remain nonzero and linearly independent, so the projected lattice contains m independent vectors of norm at most λ_n(L).Thus λ_m(L_i) ≤ λ_n(L), bounding the projected oracle output; the proof then uses monotonicity of γ.Source: §B.1 · pp. 51–52

C Statistical Distance

This section proves a product-distribution distance bound by changing coordinates through hybrids, and establishes two auxiliary claims about binary vectors and modular linear maps. It also relates the n-SMP hypothesis to the SIVP hypothesis considered by Vafa and Vaikuntanathan.

C Statistical Distance

  • The proof compares the product distributions by changing one coordinate at a time through a sequence of hybrids.The distributions are the product D_0^n and a tuple whose coordinates independently choose D_0 or D_1 with equal probability.Source: C Statistical Distance · p. 52
  • The stated n-SMP hypothesis yields a polynomial-time reduction to SIVP with an approximation factor multiplied by √n.The passage contrasts this with Vafa and Vaikuntanathan’s hypothesis, which concerns SIVP rather than n-SMP.Source: C Statistical Distance · p. 53

D.1 Proof of Claim 6.0.1

  • For the modular map, the probability of mapping to (0, 0) is N/r²; outside the ±w case, it is 1/r² or 2/r², with 1/r² for odd r.When w′ ≡ ±w (mod r), the probability is 1/r.Source: §D.1 · pp. 53–54

D.2 Proof of Claim 6.0.2

  • The span of two nonzero binary vectors that are not equal up to sign contains at most three nonzero binary vectors.Source: §D.2 · p. 54

D.3 Proof of Proposition 6.0.2

The proof counts rank-t binary matrices by encoding their dependent columns using coefficients from a bounded set. It also bounds simultaneous event probabilities using independent systems of linear equations.

D.3 Proof of Proposition 6.0.2

  • The proof counts rank-t matrices by choosing independent columns, encoding each remaining column with a coefficient vector, and permuting the columns.Invertibility of a t × t submatrix and Cramer’s rule bound the coefficient choices, yielding O(2^tn) choices for the independent columns and O((t^t2)^(m−t)) for the remaining columns, followed by a factor of m!.Source: §D.3 · p. 54

D.4 Proof of Lemma 6.0.4

  • The simultaneous-event probability is bounded by 1/(p^t1 · p^t2 · q^t3) because the corresponding linear-equation systems use independent variables.Source: §D.4 · p. 55

E.1 Proof of Lemma 7.1.1

The proof analyzes left and right sums by splitting events, using Gaussian smoothness in the central region, and averaging across residue classes. These steps support the desired estimate for the lemma.

E.1 Proof of Lemma 7.1.1

  • The proof splits the event for a left sum into left and right sum components, then applies total probability to analyze it.Source: §E.1 · pp. 55, 57
  • When the sums’ standard deviations are Θ(pq√n) and ∆ ≤ pq, shifting by ∆ stays in the central region, where f_pq,i(y) changes only by constant factors.This Gaussian smoothness property is then used in the estimate.Source: §E.1 · pp. 57–58
  • Comparing corresponding elements in residue classes, whose values differ by less than p, lets the proof average their f_pq,i values to obtain the desired result.Source: §E.1 · p. 58

E.2 Discussion on M = pqr + s

For M=pqr+s, the discussion analyzes how the remainder s affects the joint distribution of the residue variables a(pq) and a(r). It also bounds a probability involving a multinomial model in the proof of Proposition 7.0.2.

E.2 Discussion on M = pqr + s

  • For s≠0, the analysis splits each a_i into the inner range 1≤a_i≤pqr and the truncated slice pqr<a_i≤M, then studies the vectors a(pq) and a(r).Source: §E.2 · pp. 59–60
  • When s=0, a(pq)_i and a(r)_i are independent and uniform on [0,pq) and [0,r), respectively.Source: §E.2 · p. 60
  • When y=r, the residues can take only s values rather than pq values, making this the main dependence case.Source: §E.2 · p. 60

E.3 Proof of Proposition 7.0.2

  • The proof models X1, X2, and X3 with a multinomial distribution over m trials and probabilities 1/4, 1/4, and 1/2.Source: §E.3 · p. 62
  • P(|D| > c√m) ≤ 1/(2c^2) for D=X1−X2, by Chebyshev's inequality.Source: §E.3 · p. 62
Loading 2610.31056v1…