Dense Subset Sum in Multi-Dimension

Lin Chen; Tingwei Hu; Yuchen Mao; Guochuan Zhang

theoretical computer science

Dense Subset Sum in Multi-Dimension

arXiv:2607.10343

summary

The paper studies the structure of subset sums of many vectors in a multi‑dimensional integer grid, showing that when the set is sufficiently dense it contains large generalized progressions and, under a lattice‑freeness condition, all integer points of a certain zonotope, and it yields an almost‑linear time algorithm for the dense multi‑dimensional subset‑sum problem.

Abstract

We study the additive structure of dense subset sum in multi-dimension, and use the structure to develop efficient algorithms for the dense subset sum problem. More precisely, given a set $A$ of $n$ vectors in the $d$ -dimensional hyperrectangle $[N_{1}] \times [N_{2}] \times \dots \times [N_{d}]$ , we study the structure of $S (A)$ , which is the set of all subset sums of $A$ . We focus on the dense regime of the problem where $n ≫ I^¦$ and $I^¦ = N_{1} \times \dots \times N_{d}$ . We show that for any constant $d \geq 1$ , if $n ≫ I^¦$ , then $S (A)$ contains a long generalized progression in multi-dimension. If we further have that no non-trivial lattice can contain the majority of $A$ , then $S (A)$ contains all the integer points in the zonotope ${x_{1} a_{1} + \dots + x_{n} a_{n} : o (1) \leq x_{j} \leq 1 - o (1), x_{j} \in R}$ . Compared to the previous results for $d \geq 2$ , our result significantly reduces the density threshold and enlarges the region inside which all the integer points belong to $S (A)$ . Also, it matches the bound for the 1-dimensional case. Using our combinatorics result, we also develop an $O ~ (n)$ -time algorithm for the dense subset sum problem in multi-dimension.

A preliminary version to appear in FOCS'26

Topics & keywords

#subset sum #multidimensional #dense regime #additive combinatorics #algorithm designgeneralized progressionzonotopelattice‑freenessdense subset sumtilde O(n) algorithmhyperrectangle