{"ID":6536454,"CreatedAt":"2026-07-14T01:21:01.169441415Z","UpdatedAt":"2026-07-14T15:06:33.663243204Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.10343","arxiv_id":"2607.10343","title":"Dense Subset Sum in Multi-Dimension","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\\cdots\\times [N_d]$, we study the structure of $\\mathcal{S}(A)$, which is the set of all subset sums of $A$. We focus on the dense regime of the problem where $n \\gg \\sqrtΦ$ and $Φ= N_1 \\times \\cdots \\times N_d$. We show that for any constant $d\\geq 1$, if $n \\gg \\sqrtΦ$, then $\\mathcal{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 $\\mathcal{S}(A)$ contains all the integer points in the zonotope $\\{x_1\\vec{a}_1 + \\cdots + x_n\\vec{a}_n: o(1)\\leq x_j \\leq 1-o(1), x_j \\in \\mathbb{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 $\\mathcal{S}(A)$. Also, it matches the bound for the 1-dimensional case. Using our combinatorics result, we also develop an $\\tilde{O}(n)$-time algorithm for the dense subset sum problem in multi-dimension.","short_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\\cdots\\times [N_d]$, we study the structure of $\\ma...","url_abs":"https://arxiv.org/abs/2607.10343","url_pdf":"https://arxiv.org/pdf/2607.10343v1","authors":"[\"Lin Chen\",\"Tingwei Hu\",\"Yuchen Mao\",\"Guochuan Zhang\"]","published":"2026-07-11T15:08:09Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"math.CO\"]","methods":"[]","has_code":false}